Rechenungenauigkeiten

Übersicht

BlitzBasic

Allgemein

	Triton Betreff: Rechenungenauigkeiten	Mo, Okt 31, 2005 22:21 Antworten mit Zitat
Im Zuge meiner Beschäftigung mit Primzahlen und besonders mit Mersenne-Primzahlen und dem Lucas-Lehmer-test, sind mir interessante rechenungenauigkeiten von BB aufgefallen. Bei diesem Programm: https://www.blitzforum.de/viewtopic.php?p=156123 Musste ich eine eigene Funktion für 2^x schreiben, da die BB-eigene ungenau ist, selbst bei Zahlen unter 2^31. Zur Veranschaulichung: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] ; zeigt rechenungenauigkeiten von BB ; 31.20.2005 Print 1416317954 Mod 524287 Print (37634*37634-2) Mod 524287 Print (37634^2-2) Mod 524287 WaitKey Bei allen drei Zeilen müsste das gleiche rauskommen (218767). Bei der letzten ist dies aber nicht der Fall. Es kommt nur 218765 raus. Erklärungen? Kommentare?
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Betreff: Rechenungenauigkeiten

Mo, Okt 31, 2005 22:21
Antworten mit Zitat

Im Zuge meiner Beschäftigung mit Primzahlen und besonders mit Mersenne-Primzahlen und dem Lucas-Lehmer-test, sind mir interessante
rechenungenauigkeiten von BB aufgefallen.

Bei diesem Programm: https://www.blitzforum.de/viewtopic.php?p=156123
Musste ich eine eigene Funktion für 2^x schreiben, da die BB-eigene ungenau ist, selbst bei Zahlen unter 2^31.

Zur Veranschaulichung:

BlitzBasic: [AUSKLAPPEN]


;** zeigt rechenungenauigkeiten von BB
;** 31.20.2005
Print 1416317954 Mod 524287
Print (37634*37634-2) Mod 524287
Print (37634^2-2) Mod 524287
WaitKey

Bei allen drei Zeilen müsste das gleiche rauskommen (218767). Bei
der letzten ist dies aber nicht der Fall. Es kommt nur 218765 raus.

Erklärungen? Kommentare?

Coding: silizium-net.de | Portfolio: Triton.ch.vu

	Rallimen Sieger des 30-EUR-Wettbewerbs	Mo, Okt 31, 2005 22:53 Antworten mit Zitat
Mich wundert es das das letzte Ergbnis als Float ausgegeben wird, es sind doch alles nur Integerzahlen! Hab das mal getestet, Code: [AUSKLAPPEN] [EINKLAPPEN] Print 2^2 Print 1^1 Print 4^2 Print 2^1 WaitKey alles was mit ^ gerechnet wird kommt als Float raus! Demnach wird intern auf Float umgeschaltet! ein Bug?
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Mo, Okt 31, 2005 22:53
Antworten mit Zitat

Mich wundert es das das letzte Ergbnis als Float ausgegeben wird, es sind doch alles nur Integerzahlen!

Hab das mal getestet,

Code: [AUSKLAPPEN]

Print 2^2
Print 1^1
Print 4^2
Print 2^1

WaitKey

alles was mit ^ gerechnet wird kommt als Float raus!
Demnach wird intern auf Float umgeschaltet!
ein Bug?

[BB2D | BB3D | BB+]

	Dante	Mo, Okt 31, 2005 22:58 Antworten mit Zitat
hmm^^ und wenn man alles als float hat kommt überall das selbe raus... BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] Print 1416317954.0 Mod 524287.0 Print (37634*37634.0-2.0) Mod 524287.0 Print (37634.0^2.0-2.0) Mod 524287.0 WaitKey() wohl wirklich ein bug ?...

Dante

Mo, Okt 31, 2005 22:58
Antworten mit Zitat

hmm^^ und wenn man alles als float hat kommt überall das selbe raus...

BlitzBasic: [AUSKLAPPEN]

Print 1416317954.0 Mod 524287.0
Print (37634*37634.0-2.0) Mod 524287.0
Print (37634.0^2.0-2.0) Mod 524287.0 

WaitKey()

wohl wirklich ein bug ?...

Zuletzt bearbeitet von Dante am Mo, Okt 31, 2005 23:16, insgesamt einmal bearbeitet

	Rallimen Sieger des 30-EUR-Wettbewerbs	Mo, Okt 31, 2005 23:03 Antworten mit Zitat
ja, dann sind die Ergebnisse aber alle nicht genau, da definitiv 218767 rauskommen!
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Mo, Okt 31, 2005 23:03
Antworten mit Zitat

ja, dann sind die Ergebnisse aber alle nicht genau, da definitiv 218767 rauskommen!

[BB2D | BB3D | BB+]

	Buddah	Di, Nov 01, 2005 1:23 Antworten mit Zitat
Solche und ähnliche sachen sind mir auch schon aufgefallen als ich nen Baby Step Giant Step Algo geproggt hatte für Diskrete Logarithmen berechnung... hab dann auch einfach selbst eine routine geschrieben die direkt 2^irgendwas Mod irgendwas rechnet.. is ein bekannter algorithmus den man sogar aufm platt papier machen kann.. glaube von euler.. ich werd mal in meinen source codes kramen und die funktion raussuchen. Zurück zum problem.. ich denke das BB schlichtweg nicht ausgelegt ist für hoch genaue berechnungen oder rechnungen mit großen zahlen.. es ist halt für games ausgelegt und den job macht es ja gut.. gibt für jedes problem eine geeignete sprache.. und für solche probleme bietet es sich halt nicht unbedingt an BB zu benutzen wie es scheint
Alles ist gut so wie es ist und bald wird alles anders.

Buddah

Di, Nov 01, 2005 1:23
Antworten mit Zitat

Solche und ähnliche sachen sind mir auch schon aufgefallen
als ich nen Baby Step Giant Step Algo geproggt hatte für Diskrete Logarithmen berechnung... hab dann auch einfach selbst eine routine
geschrieben die direkt 2^irgendwas Mod irgendwas rechnet.. is ein bekannter
algorithmus den man sogar aufm platt papier machen kann.. glaube von
euler.. ich werd mal in meinen source codes kramen und die funktion
raussuchen.

Zurück zum problem.. ich denke das BB schlichtweg nicht ausgelegt ist
für hoch genaue berechnungen oder rechnungen mit großen zahlen.. es ist
halt für games ausgelegt und den job macht es ja gut.. gibt für jedes problem
eine geeignete sprache.. und für solche probleme bietet es sich halt nicht
unbedingt an BB zu benutzen wie es scheint Smile

Alles ist gut so wie es ist und bald wird alles anders.

	BIG BUG	Di, Nov 01, 2005 21:01 Antworten mit Zitat
Rechenungenauigkeiten muss man bei Floatberechnungen mit großen Zahlen hinnehmen, da diese aufgrund deren Abbildungstechnik im Speicher nur "angenähert" werden. Hiervon sind übrigens alle 32-Bit-Floatberechnungen betroffen, auch in anderen Programmiersprachen. Dass Exponentialrechnungen automatisch in Float erfolgen ist aber wirklich etwas unschön.
B3D-Exporter für Cinema4D!(V1.4) MD2-Exporter für Cinema4D!(final)

BIG BUG

Di, Nov 01, 2005 21:01
Antworten mit Zitat

Rechenungenauigkeiten muss man bei Floatberechnungen mit großen Zahlen hinnehmen, da diese aufgrund deren Abbildungstechnik im Speicher nur "angenähert" werden. Hiervon sind übrigens alle 32-Bit-Floatberechnungen betroffen, auch in anderen Programmiersprachen.

Dass Exponentialrechnungen automatisch in Float erfolgen ist aber wirklich etwas unschön.

B3D-Exporter für Cinema4D!(V1.4)
MD2-Exporter für Cinema4D!(final)

	TheShadow Moderator	Di, Nov 01, 2005 22:47 Antworten mit Zitat
in blitzmax hat ^ eine double-genauigkeit in anderen bb-versionen hat es float-genauigkeit und von gleitkommazahlen kann man solche genauigkeiten nicht erwarten - auch nicht in C++
AMD64 3500+ \| GeForce6600GT 128MB \| 1GB DDR \| WinXPsp2

TheShadow

Moderator

Di, Nov 01, 2005 22:47
Antworten mit Zitat

in blitzmax hat ^ eine double-genauigkeit
in anderen bb-versionen hat es float-genauigkeit

und von gleitkommazahlen kann man solche genauigkeiten nicht erwarten - auch nicht in C++

AMD64 3500+ | GeForce6600GT 128MB | 1GB DDR | WinXPsp2

	Buddah	Mi, Nov 02, 2005 4:24 Antworten mit Zitat
Wirklich genau gehts sowieso nirgends.. immerhin sind ja alle zahlen nur repräsentiert im rechner nicht wirklich abgebildet. Da kann man noch so lange register haben und die mantissen etc. ins unendliche treiben. Aber darum geht es auch garnicht denk ich.. wenn man sowas brauch is BB einfach die falsche wahl.. man siehts ja schon an den datentypen die zur auswahl stehen Hab die funktion gefunden von der ich sprach.. ist allerdings in Purebasic gecoded.. aber wird wohl jeder leicht umbauen können bei bedarf. Code: [AUSKLAPPEN] [EINKLAPPEN] Procedure.l FastExpMod(base.l,exponent.l,mod.l) Protected r.l r.l = 1 While exponent > 0 If (exponent>>1)<<1 <> exponent r = (rbase)%mod EndIf base = (basebase)%mod exponent = exponent>>1 Wend ProcedureReturn r EndProcedure Damit kann man wie gesagt "base ^ exponent mod modulo" rechnen wobei alles recht groß werden darf. Wenn man möchte kann man noch einen check einbauen ob der exponent größer als der modulo ist. Sollte das der fall sein darf man den "kürzen" auf exponent mod modulo - 1.
Alles ist gut so wie es ist und bald wird alles anders.

Buddah

Mi, Nov 02, 2005 4:24
Antworten mit Zitat

Wirklich genau gehts sowieso nirgends.. immerhin sind ja alle zahlen
nur repräsentiert im rechner nicht wirklich abgebildet. Da kann man noch
so lange register haben und die mantissen etc. ins unendliche treiben.
Aber darum geht es auch garnicht denk ich.. wenn man sowas brauch is
BB einfach die falsche wahl.. man siehts ja schon an den datentypen die
zur auswahl stehen Smile

Hab die funktion gefunden von der ich sprach.. ist allerdings in Purebasic gecoded.. aber wird wohl jeder leicht umbauen können bei bedarf.

Code: [AUSKLAPPEN]

Procedure.l FastExpMod(base.l,exponent.l,mod.l)
Protected r.l
r.l = 1
While exponent > 0
If (exponent>>1)<<1 <> exponent
r = (r*base)%mod
EndIf
base = (base*base)%mod
exponent = exponent>>1
Wend
ProcedureReturn r
EndProcedure

Damit kann man wie gesagt "base ^ exponent mod modulo" rechnen
wobei alles recht groß werden darf. Wenn man möchte kann man
noch einen check einbauen ob der exponent größer als der modulo ist.
Sollte das der fall sein darf man den "kürzen" auf
exponent mod modulo - 1.