» Forum » Programowanie » [C, C++] Szukam pomocy

Dzielenie dużych liczb.

Ostatnio zmodyfikowano 2015-06-29 00:57

Piastlis

Temat założony przez niniejszego użytkownika

» 2015-06-24 23:02:33

Czy ktoś zna jakichś sensowny algorytm na dzielenie dużych liczb? Dużych to znaczy że dzielna składa się z kilku tysięcy unsigned long long a dzielnik ma więcej niż jedno słowo unsigned long long.Jedyny pomysł jaki mam to dzielić "bit po bicie" ale trwa to tragicznie długo.

P-134051

darko202

» 2015-06-25 07:54:40

unsigned long long c++ : zakres ( 0 — +18 446 744 073 709 551 615 )

1. co znaczy "dzielna składa się z kilku tysięcy unsigned long long" ?
2. co znaczy "dzielnik ma więcej niż jedno słowo unsigned long long" ?

3.
>> "Jedyny pomysł jaki mam to dzielić "bit po bicie" "
ja dzieliłbym tzw. sposobem pisemnym
http://matematyka.opracowania.pl/dzielenie_pisemne_przez_liczby_wielocyfrowe/

to powinno być błyskawiczne tzn. złożoność ( < ilość cyfr w liczbie * C - gdzie C jakaś mała stała) myślę, ze dla liczby unsigned long long 20 cyfrowa powinno być zdecydowanie mniej niż 2000 operacji.
a to dla procesora to tyle co nic

P-134059

pekfos

» 2015-06-25 11:49:20

1. co znaczy "dzielna składa się z kilku tysięcy unsigned long long" ?

Zapewne implementuje duże liczby, 64000-bitowe i większe.

P-134063

Piastlis

Temat założony przez niniejszego użytkownika

» 2015-06-25 13:03:55

Chodzi o obliczenie pi z dużą dokładnością. Liczę ciąg który ma w mianowniku: (2*n+1)*(239*5)^(2*n+1). Reprezentacja jest trochę bardziej skomplikowana.Z 64 bitów wykorzystuję 32.Nie gubi się przeniesień przy mnożeniu dodawaniu i odejmowaniu.Przy dzieleniu w starszych 32 bitach umieszcza się resztę z poprzedniej liczby.O ile 239*5 da się pogrupować w liczby 32bitowe problem jest z 2n+1.Max to n=2147483647."Bit po bicie" to właśnie metoda pisemna ale w systemie dwójkowym.Wykonuje się w pętli odejmowanie i przesuwa bity. Trwa to kilkaset razy dłużej niż zwykłe dzielenie z uwzględnieniem reszty.

P-134064

darko202

» 2015-06-25 13:35:21

Sorry, ale nie rozumiem

Nie robiłem dzielenia, ale realizowałem kiedyś algorytm dużych silni
i pamiętam, że tak (1 000 000 !) trwało nie dłużej niż spluniecie

a 2^64 to (+18 446 744 073 709 551 615)

nawet bitowo dzielenie sposobem pisemnym to 64 * C operacji czyli niewiele
>>Zapewne implementuje duże liczby, 64000-bitowe i większe.
nawet to, to tylko pewna krotność tego co napisałem i nie powinno trwać dłużej niż spluniecie

>>Trwa to kilkaset razy dłużej niż zwykłe dzielenie z uwzględnieniem reszty.
chyba inaczej realizujesz ten algorytm pisemnego dzielenia
czy możesz go opisać ?

>> Wykonuje się w pętli odejmowanie i przesuwa bity.
no dobrze, ale jak dzielimy 11 przez 1 to robisz to

dzielna = 11
dzielnik = 1
for ( )
{
dzielna = dzielna - dzielnik
}

11 * C operacji

czy sposobem pisemnego dzielenia ?
11
- 1
-----
1
-1
----
0

2 * C operacji

P-134068

Piastlis

Temat założony przez niniejszego użytkownika

» 2015-06-25 20:41:49

Trochę teorii:
podziel 255 na 3 binarnie:

11111111 na 11

krok 1 :
przesuwasz mianownik maksymalnie w lewo

11111111
11000000

po odjęciu masz

00111111

i bit wyniku:

1

krok 2 :

przesuwasz mianownik w prawo i porównujesz

00111111
01100000

licznik za mały więc następny bit wyniku 0

10

i tak dalej:

00111111
00110000 ->101

00001111
00011000 ->1010

00001111
00001100 ->10101

00000011
00000110 ->101010

00000011
00000011 ->1010101

--------

00000000

Wynik to 85.Reszta z dzielenia to 0
I tyle obliczeń trzeba dla kilku bitów.
Oczywiście resztę odpowiednio pomnożoną trzeba dodać do następnego słowa.

Najpierw
1 przesunąć maksymalnie w lewo mianownik
2 porównać licznik i mianownik
3 jeżeli licznik większy od mianownika dodać do wyniku 1 i odjąć mianownik od licznika
4 jeżeli dzielenie nie jest skończone to przesunąć w prawo mianownik i w lewo wynik.

i tak bit po bicie
Pętla wykonywana jest tyle razy ile bitów ma mianownik a przesuwanie i odejmowanie obejmuje kilka słów.

To wszystko trwa stanowczo za długo.

Przy dzieleniu przez 1 słowo robi się tylko:
1 oblicza się przeniesienie i umieszcza je w następnym słowie
2 oblicza się wynik dzielenia.

Wszystko to tyle razy ile słów ma mianownik.

Różnica jest co najmniej kilkaset razy....
Policzenie 1 000 000! to chwilka.Mi starczyło cierpliwości tylko na 100 000! 2 min 38 sek i liczba mieści się w 50731 słowach unsigned long long. W każdym po 9 dziesiętnych cyfr znaczących. Ale jakbyś próbował policzyć 1000000!*999999! trochę by to potrwało.I wynik na pewno się nie zmieści na żadnym twardzielu...

P-134082

darko202

» 2015-06-26 09:05:30

OK masz problem :)
nadal jednak myślę, że sposób pisemnego dzielenia jest w porządku i powinien być błyskawiczny nawet dla dużych liczb.

choć oczywiście działanie na dużych liczbach trzeba zdefiniować samemu, jeśli nie możesz korzystać z biblioteki dużych liczb.

>>"tylko całkowite to bigint, jeśli także zmiennoprzecinkowe to GMP (ale to już kombajn). http://www.elektroda.pl/rtvforum/topic2559717.html
http://cpp0x.pl/forum/temat/?id=10369

opisywany problem wynika ze sposobu w jaki zapamiętujesz liczbę i realizujesz poszczególne operacje
wnioskuję to ze zdania
>>"liczba mieści się w 50731 słowach unsigned long long. W każdym po 9 dziesiętnych cyfr znaczących"

może się mylę, ale czytając pojawia się pytanie

1.
co to jest za Twór - N słów unsigned long long ( 9 dziesiętnych cyfr znaczących)
jak by to mogło wyglądać ? (prawdopodobnie klasa)

class TabBit
{
typedef unsigned long long slowo; // komorka w tablicy
....
protected:
int dl; // liczba bitów
slowo * tab; // tablica bitów
...
bool Dodawanie( TabBit b );
TabBit Dzielenie( TabBit b );
bool Mnozenie( TabBit b );
bool( TabBit b );

...

};

ale "W każdym po 9 dziesiętnych cyfr znaczących" - sugeruje ze robisz to jakoś inaczej

2.
sposób działania na zdefiniowanym typie Twór musi mieć tyle dodatkowych operacji, które generują te duże czasy, dla coraz bardziej złożonych liczb stąd coraz dłuższe czasy.
i nieefektywny algorytm, cos jak sortowanie bąbelkowe a nie np. quick-sort

3.
spójrz na
http://cpp0x.pl/forum/temat/?id=10369&p=2

w szczególności na opis realizacja dzielenia na dużych liczbach sposobem pisemnym
http://main.edu.pl/pl/user.phtml?op=lesson&n=33&page=algorytmika

jest złożoność czasowa całego algorytmu - ale nie wyświetla mi się :)

P-134097

Piastlis

Temat założony przez niniejszego użytkownika

» 2015-06-26 13:52:23

#include <iostream>
#include <cmath>

using namespace std;
unsigned long long liczba[ 1000000 ] = { 1 };
int mx = 0;
void mnozenie( unsigned long long n )
{
unsigned long long przeniesienie = 0;
for( int l = 0; l <= mx; l++ )
{

unsigned long long pomoc = liczba[ l ] * n + przeniesienie;
przeniesienie = pomoc / 1000000000;
liczba[ l ] = pomoc % 1000000000;
if( mx == l )
if( przeniesienie > 0 )
{
mx++;
liczba[ l + 1 ] = przeniesienie;
return;
}

}
}
void pisz( unsigned long long n, bool t )
{
if( t )
{

if( n <= 99999999 )
   cout << "0";

if( n <= 9999999 )
   cout << "0";

if( n <= 999999 )
   cout << "0";

if( n <= 99999 )
   cout << "0";

if( n <= 9999 )
   cout << "0";

if( n <= 999 )
   cout << "0";

if( n <= 99 )
   cout << "0";

if( n <= 9 )
   cout << "0";

}
cout << n;
}
int main()
{
for( unsigned long long n = 1; n <= 100000; n++ )
   mnozenie( n );

for( int t = mx; t >= 0; t-- )
   pisz( liczba[ t ], t != mx );

cout << endl;
cout << "Gotowe " << endl;
}

Tak wygląda program do liczenia silni.
Dane są reprezentowane w ten sposób by można było uzyskać szybko wynik w postaci dziesiętnej.Dotyczy to wszystkich działań i można go łatwo przestawić na dowolny system liczbowy.
9 cyfr dziesiętnych obliczam w około 20 taktach procesora(oczywiście dla mnożenia. Dodawanie jest szybsze).Kilka taktów bym zaoszczędził używając asemblera ale szczególnych zysków bym się nie spodziewał. Mnożenie i dzielenie przez stałą tablicy ma charakter liniowy.Jeżeli mnożysz 2 tablice chodzi o mnożenie długości tablic.
Taki program powinien być maksymalnie prosty gdyż stosowanie bardziej skomplikowanych mechanizmów tylko go spowalnia.

Oczywiście myślę o stworzeniu biblioteki obsługującej bardzo duże liczby.Jak na razie myślę że jestem w połowie drogi.Wszystkie szczegóły muszą działać jak najlepiej.

P-134099

« 1 » 2

Strona 1 z 2

Następna strona

» Forum » Programowanie » [C, C++] Szukam pomocy