[java] Logaritme berekenen van BigInteger naar BigDecimal

[raoulduke]

Ik ben een programma aan het schrijven waarin ik de logaritme van een grote integer wil berekenen. Ik gebruik een BigInteger omdat ik met erg grote getallen, dus groter dan een 64-bits long, aan het werken ben. Het grondtal van de logaritme is in principe niet van belang, alhoewel ik het liefst wil verder rekenen met 10 als grondtal.

Ik heb gekeken in de Java API in de klassen BigInteger en ook BigDecimal, omdat ik het resultaat van de logaritme-berekening als (groot) decimaal getal wil hebben. Deze beide Big* klassen bieden niet de ondersteuning voor log(). De klasse Math uit java.util biedt wel een log() functie aan, maar alleen voor het double-datatype.

Ik heb op Google de volgende queries ingevuld, maar ik kon hier op de eerste pagina's geen bruikbaar resultaat uit destilleren:
http://www.google.nl/sear...al&btnG=Google+zoeken&lr=
http://www.google.nl/sear...er&btnG=Google+zoeken&lr=

Het zelf schrijven van een functie voor het berekenen van BigInteger logaritmen lijkt me zeer interessant, maar ik wil eerst even informeren of ik misschien iets over het hoofd zie. Kennen jullie een klasse of methode die ik kan gebruiken voor het berekenen van logaritmes van Big*-getallen?

[ Voor 3% gewijzigd door raoulduke op 17-08-2004 18:38 ]

[Infinitive]

Kan je het getal in je logaritme factorizeren? Dat kan je gebruik maken van zo'n regeltje als: log (x*y) = log(x) + log(y)

Hoe naukeurig moet die log zijn overigens? Aangezien de nauwkeurigheid van de log toch vooral afhankelijk is van de most significant bits van je getal. Dan zou ik zeggen dat je 'm best naar een double kan casten.

[ Voor 51% gewijzigd door Infinitive op 17-08-2004 18:42 ]

[Alarmnummer]

Je zou misschien eens kunnen kijken naar fixedpoint oplossingen om logaritme`s te bepalen.

http://orbisstudios.com/oMathFP-1.06/docs/

[MSalters]

Je wilt een BigDecimal resultaat? Is een long niet groot genoeg? Als 10log x al 2⁶⁴ is, dan is x dus een getal van meer dan 2⁶⁴ cijfers. Ergens geloof ik niet dat je zo'n getal in een BigInteger kwijt kunt.

De volgende vraag is waarom je een dergelijke precisie wil van je log functie. Wat voegt de 6e decimaal van je log nog toe?

[Macros]

Volgens mij is het heel makkelijk. Je deelt het getal door een macht van 10, waardoor je een getal krijgt dat tussen de 0.09 en de 1.0 hebt. (de . opschuiven). Dan cast je het getal wat je overhoudt naar een double. Daar neem je de log₁₀ van. Dan dat antwoord tel je op met het aantal plekjes dat je de . hebt opgeschoven in die deling.

[raoulduke]

OK, alvast bedankt voor de uiterst behulpzame reacties!

Ik zal nog even toelichten in welke orde van grootte de getallen zich bevinden, misschien kan ik toch wel een double gebruiken en een afronding gebruiken. De grootste getallen waarmee ik nu werk zijn ongeveer (2^18)^(2^18), dit is gelijk aan 2^(18*18) = 2^324.

Waar nu vooral mijn interesse naar uitgaat is hoeveel bits ik nodig heb om bijvoorbeeld (2^17)!, dus 131072 faculteit op te slaan, dus eigenlijk:

code:

log( (2^17)! ) / log(2)

Het lijkt me dat die 131072 faculteit niet in een double past, of zou dit met kleine afrondingsverschillen toch makkelijk gaan?

[Verwijderd]

Als je Mathematica hebt (zoals ik) is dit vrij eenvoudig :

code:

log( (2^17)! ) / log(2) = 2039136.9

heb het antwoord uiteraard wel afgerond

[raoulduke]

Er zijn inderdaad een aantal berekeningen die ik statisch zou kunnen uitvoeren, zoals jij met Mathematica heb gedaan. Misschien dat ik een soort lookup-table kan implementeren, aangezien deze logaritmes niet veranderen door externe factoren. Ik ga nu eerst even zoeken naar een goed open-source wiskundepakket dat deze functies ondersteund, dit scheelt een hoop in de executietijd van mijn programma.

Nogmaals bedankt en als iemand nog meer suggesties heeft dan sta ik daar voor open, aangezien ik in mijn programma vroeg of laat toch logaritmes zal berekenen.

[edit]
Mocht iemand een goed open source programma hiervoor weten, dan sta ik open voor suggesties.

[ Voor 9% gewijzigd door raoulduke op 17-08-2004 22:02 ]

[Verwijderd]

Voor het nemen van een logaritme van grote faculteits getallen bestaat de stirling benadering:

code:

Log(N!) = N Log(N) - N

Dit blijkt voor grote N een zeer goede bendaring te zijn, en word ik in de praktijk dan ook ontzettend veel gebruikt.

zie ook: http://mathworld.wolfram.com/StirlingsApproximation.html

[ Voor 12% gewijzigd door Verwijderd op 17-08-2004 22:06 . Reden: ff een link toegevoegd ]

[Verwijderd]

/me zit te slapen en bedenkt zich nu pas

dat als je gebruik maakt van de striling benadering je helemaal geen log() nodig hebt voor jouw situatie:

code:

Log(2^x !)= 2^x ( Log(2^x) -1) = 2^x (x-1)

waarbij = natuurlijk zo leuk kronkelig isgelijkteken moet zijn.

[MSalters]

raoulduke schreef op 17 augustus 2004 @ 21:38:
OK, alvast bedankt voor de uiterst behulpzame reacties!

Ik zal nog even toelichten in welke orde van grootte de getallen zich bevinden, misschien kan ik toch wel een double gebruiken en een afronding gebruiken. De grootste getallen waarmee ik nu werk zijn ongeveer (2^18)^(2^18), dit is gelijk aan 2^(18*18) = 2^324.

Nee, 2^(18*18) = (2^18)^18, en dat is heeeel veel minder.

Overigens is het aantal bits in (2^17)! natuurlijk heel simpel af te schatten. Dat is namelijk 16*(2^17), omdat 16 het gemiddeld aantal bits is wat je nodig hebt voor de voorafgaande 2^17 getallen. Stirling is nauwkeurger, maar dat moet je maar net weten.

[ Voor 22% gewijzigd door MSalters op 18-08-2004 19:49 ]