[ C ] implementacja długich liczb

Odpowiedz Nowy wątek
2006-10-25 12:40
0

mam następujacy problem:

musze zaimplementowac w C mnożenie dlugich liczb (do 50 000 znakow) a za bardzo nie wiem jak sie do tego zabrac. Czy ktos spotkal sie juz z tym problemem?? jakies pomysly?? prosze o pomoc... :|

Pozostało 580 znaków

2006-10-25 13:05
0

Np. tak jak sie to robilo w podstawowce - mnozenie pisemne.

pozdrawiam
johny


You need to learn how to walk
before you can run

Pozostało 580 znaków

2006-10-25 13:12
krajek
0
<url>www.main.edu.pl</url&gt;

Taw w dziale Kursy->Algorytmika jest to ładnie opisane.

Pozostało 580 znaków

2006-10-25 19:03
Mgr.Dobrowolski
0

Ja bym tylko poradził zamiast
p += a[j]*b[i] + c[j+i];
c[j+i] = p % RADIX;
p /= RADIX

napisać<code>
p += a[j]*b[i] + c[j+i];
t = p/RADIX;
c[j+i] = p - t*RADIX;
p = t;

Będziemy tu być może nawet 2'500'000'000 razy.
Czy istnieje kompilator który by na i86 załatwił to jedną instrukcją dzielenia?

Pozostało 580 znaków

2006-10-26 14:17
0

http://carramba.homelinux.org/ftp/4programmers/vlong.zip

kiedys to bylo w downloadzie do dopisania pozostala wciaz oblsuga liczb ujemnych + ew. potegowanie


Linuksa, czy innego Uniksa, można opisać za pomocą logiki boolowskiej a nie za pomocą prawdopodobieństwa.

'System szesnastkowy jest wspaniały! W skali od 1 do 10 daję mu E'

extreme safety for Ubuntu:
sudo echo -e 'Defaults targetpw\nDefaults timestamp_timeout=0' >> /etc/sudoers

Pozostało 580 znaków

2006-10-27 10:38
0

Link podany przez Krajeka jest rzeczywiście godny polecenia. Warto podumać o Karatsubie, szkoda, że nie wspomniano o FFT. W parę minut napisałem sobie jak może wyglądać mnożenie. 50'000 dziewiątek podnoszę do kwadratu, wyszło 283 sekund, z poprawką Dobrowolskiego 181 sek (warto pamiętać, że dzielenie całkowitoliczbowe jest najwolniejszą operacją na i86).
radix
100 49,86
1000 20,87
10000 11,16
z 4:43 zrobiło się 11 sekund
Mój kompilator bardzo nieefektywnie liczy na 64 bitach. Warto sprawdzić jak twój kompilator (i procesor) sobie z tym radzi. Może się okazać się, że lepiej pozostać przy 32 bitach. Wtedy radix=10'000 jest dobrym wyborem, ponieważ 10'0002 < 232.
Mnożenie na sposób Fourier'a poradziło sobie w mniej niż sekundę.

Pozostało 580 znaków

2006-10-31 21:26
lL
0

http://swox.com/gmp/

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0