Avatar billede mollevp Nybegynder
19. januar 2006 - 23:54 Der er 5 kommentarer og
1 løsning

Mindste binære tal mellem to tal

Hej det er ikke lige java specifikt, men håber I kan hjælpe alligevel.
Jeg sidder med et optimerings problem, jeg skal finde det tal, mellem to andre tal, der har den mindste binære repræsentation:

Nogle der kender en algoritme til dette?

Eksempel jeg har:

low_number = 211/3125
high_number = 43/625

Jeg skal nu finde et tal imellem: fx. 0.068359375 svarende til 0.000100011

Håber i har nogle gode ideer
Avatar billede tjp Mester
20. januar 2006 - 01:05 #1
Hvad mener du lige med 'mindste binære repræsentation'?
Og på hvor mange cifre?
Avatar billede mollevp Nybegynder
20. januar 2006 - 01:35 #2
Jeg vil gerne finde det tal der skal bruge det mindste antal bit..
Jeg sad lige og legede lidt med lommeregneren, måske der er nogle af jer der kan forklare mig følgende:

jeg indtaster: 211/3125 = 0.06752 og får 0.000100011 som binær.
jeg indtaster: 35/512 = 0.068359375 og får 0.000100011 som binær.

Hvorledes kan det være at disse to brøker giver samme decimal repræsentation, burde man ikke kunne repræsentere disse to tal unikt binært?

Lommeregneren er Gcalctool 5.5.42 (fra Gnome)

>> Og på hvor mange cifre?

Tja, godt spørgsmål.. ligeså mange som kan ligge i en float. Jeg er lidt ude efter den algoritme som lommeregneren bruger.. Håber i kan hjælpe - ellers må jeg jo til at kigge source :)
Avatar billede mollevp Nybegynder
20. januar 2006 - 01:36 #3
Update:
>>>>
Hvorledes kan det være at disse to brøker giver samme binære repræsentation, burde man ikke kunne repræsentere disse to tal unikt binært?
<<<<
Avatar billede tjp Mester
20. januar 2006 - 01:59 #4
Det skyldes antallet af cifre som lommeregneren benytter, altså 10, begrænser præcisionen.
Hvis vi opløser det binære tal 0,000100011 i dets dele fås:

bin 0,0001      = dec 0,0625
bin 0,00000001  = dec 0,00390625
bin 0,000000001 = dec 0,001953125

hvilket giver 0,068359375, når vi lægger decimaltallene på højreside sammen.
Hvis sidste bit ikke er sat, altså 0,000100010, får vi værdien 0,0625 + 0,00390625 = 0,06640625.
Følgende viser at dette tal ligger længere væk fra 0,06752 end 0,068359375:

0,06640625  + 0,00111375  = 0,06752
0,068359375 - 0,000839375 = 0,06752

0,068359375 således er det nærmeste vi kan komme 0,06752 binært, og derfor har de to tal samme repræsentation.
Avatar billede mollevp Nybegynder
20. januar 2006 - 03:05 #5
Takker for svaret. Det ser fornuftigt ud.. Jeg kunne dog stadig godt tænke mig at vide hvordan lommeregneren finder frem til tallet?
Avatar billede tjp Mester
20. januar 2006 - 15:31 #6
Lommeregneren finder faktisk ikke frem til det binære tal - den arbejder binært, blot med en højere præcision end de 10 cifre som displayet giver, og "oversætter" normalt resultatet til decimaltal bagefter. Er det en algoritme til at omregne decimaltal til binære du ønsker?
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester