[Java] Hoe met extreem grote getallen te werken? *

[Verwijderd]

hallo,

ik ben bezig met java om een programma te schrijven die een getal kan ontbinden in 2 priemgetallen. maar het probleem is niet het programma, maar de grenzen ervan. de uitdaging wordt namelijk leuker als je enorme getallen neemt, getallen met meer dan 50 t/m 250 cijfers bv. (ja indd, daar kan je veel geld mee verdienen)

ik zit dus met een probleem. int gaat niet verder dan een schaal van miljard ofzo (zeg: 10 cijfers) en double gaat niet verder dan enkele miljarden (zeg: 15 cijfers max)

vandaar dus mijn vraag: zijn er manieren om toch aan de slag te kunnen gaan met getallen van 35 ziljoen-megatriljard zeg maar? (plug-in misschien?)

bedankt

(btw: de gever van de gouden tip zal ik niet vergeten als ik die prijs van $10.000 ga incasseren )

//edit
de prijsvraag heeft te maken met het beveiligen van bank-data...een bank gebruikt daar in principe 2 getallen voor, getal A en getal B. en A*B=C
C is publiekelijk. maar C is dat onbenullig grote getal. verder is gegeven: A en B zijn priemgetallen.....succes, heb je A en B gevonden, laat het de banken weten en je verkoopt hun je programma.

[ Voor 21% gewijzigd door Verwijderd op 13-10-2004 20:08 ]

[Spider.007]

Kan ik een deel incasseren door je vraag te verplaatsen naar een subforum waar wat meer mensen er vanaf weten?

[probleem met java] onbenullig grote getallen > [Java] Hoe met extreem grote getallen te werken? *
SA > PW

[Casteloni]

Dan moet je zelf een eigen klasse schrijven die dat wel kan doen

Je zou bijvoorbeeld een klasse Getal kunnen schrijven waar je 1000 getallen in kan opslaan. Vervolgens maak je net zo veel objecten aan totdat je je hele getal kwijt bent. Die objecten kan je bijvoorbeeld in een hashmap plaatsen.

Ik weet alleen niet wat handig is als je naar de performance gaat kijken.

[roelio]

Heb je al eens in java.Math rondgekeken?
http://www.javacoffeebreak.com/faq/faq0031.html

[CyBeR]

Zoek eens op de BigInteger class?

edit:

Volledige naam ipv afkorting

[ Voor 44% gewijzigd door CyBeR op 10-10-2004 21:16 ]

[tharkun]

Wat je ook kan doen is een getal als een string opslaan. bewerkingen doe je dan door te cijferen.

[Macros]

Alle antwoorden zijn relatief dom, alleen dat van CyBeR is goed. Je moet BigInteger gebruiken.

[Alarmnummer]

Verwijderd schreef op 10 oktober 2004 @ 20:47:
hallo,

ik ben bezig met java om een programma te schrijven die een getal kan ontbinden in 2 priemgetallen. maar het probleem is niet het programma, maar de grenzen ervan. de uitdaging wordt namelijk leuker als je enorme getallen neemt, getallen met meer dan 50 t/m 250 cijfers bv.

Priemgetallen bereken wordt al erg lang gedaan en ze zijn verder dan jij op jouw pc in een mensenleven kan berekenen. Ik neem aan dat er vast wel een of andere database is waar je kunt controleren of jouw getal wel of geen priemgetal is.

(ja indd, daar kan je veel geld mee verdienen)

Zie verder ook de Bigint zoals hierboven (oa door Limoentje) is genoemt.

[ Voor 6% gewijzigd door Alarmnummer op 10-10-2004 22:47 ]

[Macros]

Als die jongen nou een super slim nieuw algoritme in zijn hoofd heeft zitten, dan moeten we hem natuurlijk niet tegen houden

[CyBeR]

Alarmnummer schreef op 10 oktober 2004 @ 22:47:
[...]

Priemgetallen bereken wordt al erg lang gedaan en ze zijn verder dan jij op jouw pc in een mensenleven kan berekenen. Ik neem aan dat er vast wel een of andere database is waar je kunt controleren of jouw getal wel of geen priemgetal is.

Vast wel. Maar ontbinden is niet hetzelfde als checken of een getal priem is

[McFreak]

matrixes maken, tijd voor wiskunde

[Verwijderd]

CyBeR schreef op 10 oktober 2004 @ 22:53:
[...]


Vast wel. Maar ontbinden is niet hetzelfde als checken of een getal priem is

Klopt, das meer cryptografie. Daar zijn ze waarschijnlijk ook al verder mee dan hij op zijn pc

Kan dat overigens niet veel sneller met een functionele programmeertaal als haskel ofzo?

[Macros]

Functionele en logische talen zijn meestal langzamer. Talen zoals C en C++ zullen waarschijnlijk het snelst gaan, maar eigenlijk is het niet belangrijk. Want de snelheid van je algoritme is het belangrijkst.

[Alarmnummer]

Macros schreef op 10 oktober 2004 @ 23:04:
Functionele en logische talen zijn meestal langzamer. Talen zoals C en C++ zullen waarschijnlijk het snelst gaan, maar eigenlijk is het niet belangrijk.

Op het gebied van numeriek rekenen is er maar 1: fortran

Want de snelheid van je algoritme is het belangrijkst.

Yep.. helemaal mee eens.

[Verwijderd]

Macros schreef op 10 oktober 2004 @ 22:39:
Alle antwoorden zijn relatief dom, alleen dat van CyBeR is goed. Je moet BigInteger gebruiken.

Kan dit dan niet simpel met Perl ?
HAHAHA

[Macros]

Perl schakelt automagisch over naar BigInteger bij grote getallen en is in het algemeen 100x langzamer dan C.
HAHAHA

[Daventry]

Sun zou er goed aan doen die BigInteger klasse eens een beetje werkbaar te maken. Heb het ding een keer gebruikt en nu, een half jaar later, er nog nachtmerries van

[Verwijderd]

Macros schreef op 11 oktober 2004 @ 09:35:
Perl schakelt automagisch over naar BigInteger bij grote getallen en is in het algemeen 100x langzamer dan C.
HAHAHA

Je begrijpt me verkeerd. Ik zat te denken aan een rexeg die een groot getal splitst in priemfactoren.

[Verwijderd]

Verwijderd schreef op 11 oktober 2004 @ 13:39:
[...]

Je begrijpt me verkeerd. Ik zat te denken aan een rexeg die een groot getal splitst in priemfactoren.

HAHAHA

Das dan ongeveer 1000x langzamer dan C. Sinds wanneer kun je snel rekenen met regexen...

Standaard (simpel) algoritme voor dit soort dingen is alle priemgetallen van 1 tot sqrt(factor) aflopen, factor delen door priem en kijken of het resultaat een heel getal is. Hoe wil jij dat doen met een regex?

edit:
Oh en het algo kan vast geoptimaliseerd worden, maar het gaat even om het idee hea

[ Voor 10% gewijzigd door Verwijderd op 11-10-2004 13:44 ]

[Verwijderd]

Verwijderd schreef op 11 oktober 2004 @ 13:43:
[...]
Standaard (simpel) algoritme voor dit soort dingen is alle priemgetallen van 1 tot sqrt(factor) aflopen, factor delen door priem en kijken of het resultaat een heel getal is. Hoe wil jij dat doen met een regex?

edit:
Oh en het algo kan vast geoptimaliseerd worden, maar het gaat even om het idee hea

[ironisch]
Met Perl kan je toch zoeken op voorkomen van textpatronen ? Bv het aantal voorkoment "to" tellen in Toentomatentomatentomatentovrat.
Kan ik dan met Perl niet zoeken naar priemfactoren in "8735284764532857" ? Dat zou me hevig teleurstellen .
[/ironisch]

[Verwijderd]

bedankt voor alle tips...de een beter dan de ander (zul je altijd zien )
maar al het gedoe rondom priemgetallen is niet eens het moelijkste. het gaat om het ontbinden...een kick-ass algorithme voor dergelijke getallen is moeilijk...omdat ik dus ook niet beschik over een mainframe. ook als ik niet ga meedoen aan getallen tot 200 cijfers en verder, blijft het moeilijk om snel een goed resultaat te krijgen.

in mijn hoofd begint zich overigens al wel een wijs algorithme te vormen..maar ik zeg niks totdat ik in mijn villa, met een cocktailtje op mijn luchtkrokodil in mijn eigen subtropische zwembadje lig

bedankt iig

btw - aan de mensen die wel een gewerkt hebben met bigint:
is dat oneindig? lijkt me niet, dus waar ligt de grens dan? bij 99^99 ofzo?

[ Voor 10% gewijzigd door Verwijderd op 13-10-2004 20:05 ]

[Macros]

Bigint is gelimiteerd aan het geheugen in je computer. Dus stel je hebt 4 megabyte, dan kan je getallen aan van: 2^4194304

[Zoijar]

Verwijderd schreef op 13 oktober 2004 @ 19:55:
in mijn hoofd begint zich overigens al wel een wijs algorithme te vormen..maar ik zeg niks totdat ik in mijn villa, met een cocktailtje op mijn luchtkrokodil in mijn eigen subtropische zwembadje lig

Hehe, ik wil je droom en enthousiasme eigenlijk niet verstoren....maar denk je niet dat er ook wiskundige etc. aan dit soort dingen werken? Dat is geen prijsvraag van de bank; dat is om te laten zien dat het wel degelijk veilig is, reclame dus Een goed 'snel' algoritme hiervoor zou de wereld op zijn kop zetten. En dan bedoel ik dus niet een jaar rekenen met een cluster...

Er is geen polynomiale oplossing bekend op huidige computers. Echter is er theoretisch eentje op quantum computers; maar daar zouden error correctie ed. wel eens roet in het eten kunnen gooien.

Geen grens idd, er wordt gewoon gewerkt met een string. Bv "1234" daar kan je de string "2345" bij optellen. Gewoon per getal, en dan alles boven de tien 'meenemen'. Net zoals je het op papier doet. Overigens worden er vaak wel slimmere snellere algoritmes gebruikt, maar dat doet er even niet toe.

[Infinitive]

Er bestaat geen regex waarmee je kan bepalen of een willekeurig getal n een priemgetal is. Daar is de taal van regexen niet krachtig genoeg voor

[Zoijar]

Infinitive schreef op 13 oktober 2004 @ 21:05:
Er bestaat geen regex waarmee je kan bepalen of een willekeurig getal n een priemgetal is. Daar is de taal van regexen niet krachtig genoeg voor

Dat wou ik eerst ook zeggen, maar Perl heeft uitgebreide regexen, die een taal defineeren die sterker is dan een reguliere.

[ACM]

Regexp, ook van perl, is een tekstmanipulatietaal, niet een rekentaal. Je kan er dus helemaal geen patronen uithalen als "x is deelbaar door 3" (nahja, tenzij je met een callback de losse cijfers optelt en dat herhaalt net zolang tot je 3, 6 of 9 krijgt ), wel hele complexe varianten van "x bevat het cijfer 3".

[Zoijar]

ACM schreef op 13 oktober 2004 @ 22:03:
Regexp, ook van perl, is een tekstmanipulatietaal, niet een rekentaal. Je kan er dus helemaal geen patronen uithalen als "x is deelbaar door 3" (nahja, tenzij je met een callback de losse cijfers optelt en dat herhaalt net zolang tot je 3, 6 of 9 krijgt ), wel hele complexe varianten van "x bevat het cijfer 3".

Tsja, volgens mij kan je er een turing machine in simuleren...weet ik niet helemaal zeker, misschien dat het 'slechts' context vrij oid is en niet recursief enumerabel...maar dan kan je dus alles doen wat je wilt in principe Zelfs een perl interpreter schrijven...anyway, het doet er niet toe

[Soultaker]

Macros schreef op 13 oktober 2004 @ 20:51:
Bigint is gelimiteerd aan het geheugen in je computer. Dus stel je hebt 4 megabyte, dan kan je getallen aan van: 2^4194304

VM geheugen, neem ik aan, en dat kan ook best virtueel (swap) geheugen zijn. Wat dat betreft is er dus feitelijk geen limiet dan je vrije harde schijf ruimte (aangenomen dat je een 64-bits OS hebt, anders houdt het met 2 of 3 GB ook wel op).