---

Jeg er helt nu hvad angår c++ og har et lille problem.

Jeg vil gerne faktorisere et meget stort tal, x, på 120 cifre, og har
derfor brug for at kunne lave heltalsdivision med tal på 60 cifre, da jeg
ved, at tallet er sammensat af to primtal på hver 60 cifre.

Er der en standardmåde til at arbejde med så store tal på?

Med venlig hilsen

Jes Hansen

---

Jes Hansen skrev:

>Er der en standardmåde til at arbejde med så store tal på?

Det ved jeg ikke, og jeg ved heller ikke om der findes nogle
moduler med færdige rutiner i, men jeg bruger arrays med tal i
hvor hvert element skal holde styr på f.eks. tre cifre (passer
med udskrift med skilletegn). Så skal man bare programmere de
fire regningsarter selv og holde styr på menterne. Det er ikke så
svært.

--
Bertel
Hvis mine indlæg mangler luft, skyldes det serverproblemer.
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

> Det ved jeg ikke, og jeg ved heller ikke om der findes nogle
> moduler med færdige rutiner i,

Det gør der skam, prøv at søge på "arbitrary precision" librarys,
jeg ved ikke hvor lette de er at gå til for nybegyndere ;)

> men jeg bruger arrays med tal i
> hvor hvert element skal holde styr på f.eks. tre cifre (passer
> med udskrift med skilletegn). Så skal man bare programmere de
> fire regningsarter selv og holde styr på menterne. Det er ikke så
> svært.

Har du lavet en divisionsalgoritme?
Kan man få et par hints ;)

---

SuneF skrev:

>Har du lavet en divisionsalgoritme?

Det tror jeg nok.

>Kan man få et par hints ;)

Gør som i hånden:
Opret arrays til dividend, divisor og resultat. Tag så mange
elementer af dividenden som der er elementer i divisor (kan evt.
give 0 første gang), sjus dig til en faktor, gang ud (v.h.a. din
gangealgoritme) og træk fra. Hvis det bliver negativt, så læg
divisor til én gang. Tilføj et element mere til divisor. Gentag.

--
Bertel
Fejl med (manglende/ekstra) tomme linjer skyldes serverproblemer.
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

> >Har du lavet en divisionsalgoritme?
>
> Det tror jeg nok.
>
> >Kan man få et par hints ;)
>
> Gør som i hånden:
[....]

Fedt nok, det vil jeg da prøve ved lejlighed.
Jeg har nemlig også lavet en lille util som kan
addere, subrtrahere, multiplicere lave fakulter, moduloer og potensopløfte.

De fleste ting kan gøres i en vilkårlig radix imellem 2 og 1.000.000.000
Jeg har bare anvendt FFT til multipliceringerne, ellers tager det en evighed
( det er jo kun en O(N^2) algoritme).
Jeg har faktisk begregnet 33.333.333! med programmet, og verificeret
de føste cifre med Stirlings formel.
Jeg manglede bare en divisionsalgoritme ;)

---

"SuneF" <noluck@nowhere.dk> writes:

> Jeg manglede bare en divisionsalgoritme ;)

Knuth, "The Art of Computer Programming", vol.2, p. 272.

--
Jens Axel Søgaard -- http://www.jasoegaard.dk

A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös

---

> > Jeg manglede bare en divisionsalgoritme ;)
>
> Knuth, "The Art of Computer Programming", vol.2, p. 272.

Ja men hvis jeg skulle købe en bog hver gang et lille problem skulle løses....

---

"SuneF" <noluck@nowhere.dk> writes:

> Ja men hvis jeg skulle købe en bog hver gang et lille problem skulle
> løses.

http://www.cacr.math.uwaterloo.ca/hac/

Kapitel 14.

---

> http://www.cacr.math.uwaterloo.ca/hac/
>
> Kapitel 14.

Ser det ser det ;)

http://www.nr.com

Andre som har fede links?

---

"SuneF" <noluck@nowhere.dk> writes:

> > > Jeg manglede bare en divisionsalgoritme ;)
> >
> > Knuth, "The Art of Computer Programming", vol.2, p. 272.
>
> Ja men hvis jeg skulle købe en bog hver gang et lille problem skulle
> løses....

Biblioteket.

Desuden, er Knuth en af den slags, man skal have stående

Når du kan lide at programmere beregninger med store tal, tror jeg, at
du vil kunne lide Knuth.

--
Jens Axel Søgaard -- http://www.jasoegaard.dk

A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös

---

Jens Axel Søgaard skrev:

>Desuden, er Knuth en af den slags, man skal have stående

.... og samle støv?

>Når du kan lide at programmere beregninger med store tal, tror jeg, at
>du vil kunne lide Knuth.

Hm, jeg synes at der er et noget langt spring fra at kunne lide
store tal og så få fuldt udbytte af Knuth. Der er mange andre
bøger som er nemmere tilgængelige.

--
Bertel
Fejl med (manglende/ekstra) tomme linjer skyldes serverproblemer.
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen <nospamto@lundhansen.dk> writes:

> Jens Axel Søgaard skrev:
>
> >Desuden, er Knuth en af den slags, man skal have stående
>
> ... og samle støv?
>
> >Når du kan lide at programmere beregninger med store tal, tror jeg, at
> >du vil kunne lide Knuth.
>
> Hm, jeg synes at der er et noget langt spring fra at kunne lide
> store tal og så få fuldt udbytte af Knuth. Der er mange andre
> bøger som er nemmere tilgængelige.

Han kan jo låne den og se om han kan lide den. Det jeg "triggede" på var:

"Ja men hvis jeg skulle købe en bog hver gang et lille problem
skulle løses...."

Se her kommer Knuth ind i billedet. Knuth er enormt god at slå op i.

--
Jens Axel Søgaard -- http://www.jasoegaard.dk

A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös

---

Jens Axel Søgaard skrev:

>Se her kommer Knuth ind i billedet. Knuth er enormt god at slå op i.

Men stadig avanceret. Jeg har faktisk 'læst' de tre bind, og har
dem endda liggende, men det meste er over mit niveau (eller
kræver adgang til en underviser og en studiegruppe hvilket jeg
ikke har haft). Jeg har haft meget mere ud af "Algorithms" af
Robert Sedgewick. Hvis man synes at den er for nem, kan man
opgradere til Knuth.

--
Bertel
Fejl med (manglende/ekstra) tomme linjer skyldes serverproblemer.
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen <nospamto@lundhansen.dk> writes:

> Jens Axel Søgaard skrev:
>
> >Se her kommer Knuth ind i billedet. Knuth er enormt god at slå op i.
>
> Men stadig avanceret. Jeg har faktisk 'læst' de tre bind, og har
> dem endda liggende, men det meste er over mit niveau

Jo jo, det er de færreste der får det hele med. Man kan dog komme
langt med pluklæsning og saksning af algoritmerne (man behøver jo ikke
læse om for eksempel korrekthed og tidsforbrug for at anvende dem i
praksis). Jeg kan godt lide, at der er "noget ekstra". Det giver een
en fornemmelse af, hvad man kan gøre for at komme videre.

> (eller kræver adgang til en underviser og en studiegruppe hvilket
> jeg ikke har haft). Jeg har haft meget mere ud af "Algorithms" af
> Robert Sedgewick.

Den kender jeg desværre ikke.

> Hvis man synes at den er for nem, kan man opgradere til Knuth.

Hvis det ikke lige var emnet "beregning med store tal" havde jeg nok
heller ikke foreslået Knuth. Det var simpelthen den bedste bog om
emnet, jeg havde på reolen.

--
Jens Axel Søgaard -- http://www.jasoegaard.dk

A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös

---

Bertel Lund Hansen <nospamto@lundhansen.dk> skrev den 28-May-01:

> Hm, jeg synes at der er et noget langt spring fra at kunne lide
> store tal og så få fuldt udbytte af Knuth. Der er mange andre
> bøger som er nemmere tilgængelige.

Nemmere tilgængelig, jovist. Men bøger af Knuth, Meyers, Stroustrup og
Stevens (for at nævne nogle stykker) er bøger man vender tilbage til
gang på gang. Let tilgængelige bøger er gerne en engangsforestilling.


Ovenstående er selvfølgelig ikke andet end min personlige og
utvivlsomt for nogen højrøvede fremlæggelse af lærebogssituationen.
Men som fattig studerende må man prioritere sine bogindkøb, og jeg
føler afgjort at jeg får mest "bang per buck" hos de velkendte
forfattere.

--
Regards, Anders

....if a Microsoft product fails, who do you sue?

---

Anders Melchiorsen <c960452@student.dtu.dk> writes:

> Nemmere tilgængelig, jovist. Men bøger af Knuth, Meyers, Stroustrup og
> Stevens (for at nævne nogle stykker) er bøger man vender tilbage til
> gang på gang. Let tilgængelige bøger er gerne en engangsforestilling.

Set i forhold til Knuth er de fleste algoritme-bøger vel
lettilgængelige?

Der findes da glimrende alternativer der er lettere at forstå:

Sedgewicks Algoritme bøger
Cormen/Rivest/Leiserson "Introduction to Algorithms"

fortrækker jeg til enhver tid fremfor Knuth.

---

"Jes Hansen" <jeshansen@mail.dk> writes:

> Jeg er helt nu hvad angår c++ og har et lille problem.
>
> Jeg vil gerne faktorisere et meget stort tal, x, på 120 cifre, og har
> derfor brug for at kunne lave heltalsdivision med tal på 60 cifre, da jeg
> ved, at tallet er sammensat af to primtal på hver 60 cifre.
>
> Er der en standardmåde til at arbejde med så store tal på?

Nej.

Hvad med at kigge på GNU's MP:

<http://www.gnu.org/software/gmp/gmp.html>?

Eller bruge Scheme i stedet for C

--
Jens Axel Søgaard -- http://www.jasoegaard.dk

A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös

---

> Jeg er helt nu hvad angår c++ og har et lille problem.
>
> Jeg vil gerne faktorisere et meget stort tal, x, på 120 cifre, og har
> derfor brug for at kunne lave heltalsdivision med tal på 60 cifre, da jeg
> ved, at tallet er sammensat af to primtal på hver 60 cifre.

Kender du disse primtal?
Du kan nemlig ikke anvende denne metode til at finde de to primtal.

---

> Kender du disse primtal?
> Du kan nemlig ikke anvende denne metode til at finde de to primtal.

Nej. Men da tallet er sammensat af kun to tal, vil man så ikke kunne begynde
fra en ende af og dividere 10^60+1 og og se på resten ved divisionen?

Jeg kunne godt forestille mig, at tallet måske er sammensat af to primtal
der ligger ved siden af hinanden, så jeg ville starte med sqrt(x) og så
arbejde mig nedad.

Med venlig hilsen

Jes Hansen

---

On Sun, 27 May 2001 19:53:39 +0200,
Jes Hansen <jeshansen@mail.dk> wrote:

>> Kender du disse primtal?
>> Du kan nemlig ikke anvende denne metode til at finde de to primtal.
>
>Nej. Men da tallet er sammensat af kun to tal, vil man så ikke kunne begynde
>fra en ende af og dividere 10^60+1 og og se på resten ved divisionen?
>
>Jeg kunne godt forestille mig, at tallet måske er sammensat af to primtal
>der ligger ved siden af hinanden, så jeg ville starte med sqrt(x) og så
>arbejde mig nedad.

Jeg håber du har en _meget_ hurtig computer :) Prøv lige at regne lidt
på hvor lang tid det vil tage.

--
Anders Bo Rasmussen mailto:fuzz01@spamfilter.dk
Frimestervej 42 1.tv http://www.fuzz.dk
2400 Kbh. NV
Denmark

---

fuzz01@spamfilter.dk (Anders Bo Rasmussen) writes:

> Jeg håber du har en _meget_ hurtig computer :) Prøv lige at regne lidt
> på hvor lang tid det vil tage.

Vi kan jo gøre det for Jes
Hvis vi optimistisk antager at der findes en primfaktor mellem 10^59
og 10^60. Så skal vi altså teste 10^60 - 10^59 = 9 * 10^59 tal. Vi
kan vist hurtigt blive enige om at de lige tal kan springes over. Så
har vi "kun" 4,5 * 10^59 tal at checke.

God fornøjelse siger jeg bare!

Jeg ville nok se på en lidt mere avanceret faktoriseringsalgoritme end
den der er beskrevet. Jeg har ladet mig fortælle at quadratic sieve
ikke skulle være helt umulig at implementere (jeg har ikke selv
forsøgt), men det kommer nok til at tage lidt tid alligevel.

--
Jacob
"Huh? I don't understand this at all."
-- CRITIC Reject code from RFC 2795

---

Den Sun, 27 May 2001 19:53:39 +0200 skrev Jes Hansen:
>> Kender du disse primtal?
>> Du kan nemlig ikke anvende denne metode til at finde de to primtal.
>
>Nej. Men da tallet er sammensat af kun to tal, vil man så ikke kunne begynde
>fra en ende af og dividere 10^60+1 og og se på resten ved divisionen?
>
>Jeg kunne godt forestille mig, at tallet måske er sammensat af to primtal
>der ligger ved siden af hinanden, så jeg ville starte med sqrt(x) og så
>arbejde mig nedad.

Du kan altid starte ved sqrt(x) og arbejde nedaf.

De ene af de to tal vil altid være <= sqrt(x), og det andet vil altid
være >=sqrt(x), og når du har det ene, er det andet nemt at finde.

Mvh
Kent
--
http://www.celebrityshine.com/~kfr/

---

Kent Friis skrev:


>være >=sqrt(x), og når du har det ene, er det andet nemt at finde.


Ja, i princippet. Det er kun et spørgsmål om tid ...


--
Bertel
Fejl med (manglende/ekstra) tomme linjer skyldes serverproblemer.
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

> > Kender du disse primtal?
> > Du kan nemlig ikke anvende denne metode til at finde de to primtal.
>
> Nej. Men da tallet er sammensat af kun to tal, vil man så ikke kunne begynde
> fra en ende af og dividere 10^60+1 og og se på resten ved divisionen?

Nej! Selv om du havde hele klodes samlede computerkraft ville du ikke kunne finde
den divisor i en menneskealder.
Prøv at tænke en gang:
De to tal har 60 cifre hver, du kender tallet (X) og kan finde sqrt(X).
Nu skal du bare undersøge alle tal imellem 10^60 og sqrt(X).
Selvom du udlader alle de åbenlyse små tabeller: 2,3,5,7,11,...
Så bliver der stadig ufattelig mange tilbage.

> Jeg kunne godt forestille mig, at tallet måske er sammensat af to primtal
> der ligger ved siden af hinanden, så jeg ville starte med sqrt(x) og så
> arbejde mig nedad.

Hmm, ja hvis primtallene er naboer, så er det en helt anden snak!
Så kan du bare tage sqrt(X) og så køre lidt op eller ned til du støder på en divisor
(thi den ene må jo være lidt større end sqrt(X) og den anden lidt mindre).

---

"Jes Hansen" <jeshansen@mail.dk> writes:

> Jeg er helt nu hvad angår c++ og har et lille problem.

Et lille problem?

> Jeg vil gerne faktorisere et meget stort tal, x, på 120 cifre, og har
> derfor brug for at kunne lave heltalsdivision med tal på 60 cifre, da jeg
> ved, at tallet er sammensat af to primtal på hver 60 cifre.

Så vidt jeg ved, så ville du, hvis du fandt en effektiv algoritme til
det der, være rimelig godt på vej mod at bryde en seriøs del af den
kryptering der er i verden, da den baserer sig på store primtal.

Prøv at tage et par matematik og datalogi kurser på universitet, de vil
sikkert kunne hjælpe dig et stykke af vejen. Eller også vil du bare indse,
at det er praktisk taget umuligt, at gætte to primtal, hvis du ikke kender
det ene

Med venlig hilsen

- Jacob Atzen

---

"Jes Hansen" <jeshansen@mail.dk> wrote:

>Jeg er helt nu hvad angår c++ og har et lille problem.
>
>Jeg vil gerne faktorisere et meget stort tal, x, på 120 cifre, og har
>derfor brug for at kunne lave heltalsdivision med tal på 60 cifre, da jeg
>ved, at tallet er sammensat af to primtal på hver 60 cifre.
>
>Er der en standardmåde til at arbejde med så store tal på?
>
>Med venlig hilsen
>
>Jes Hansen

Når du har løsningen kan der på forskellig måde være gode penge i det.
For eksempel 200.000$, hvis du går op til 617 cifre:

http://www.rsasecurity.com/rsalabs/challenges/factoring/index.html

--
Svend Olaf