Mnożenie Karatsuba dla nierównych rozmiarów, operatory bez mocy.

Jaki jest najskuteczniejszy sposób implementacji Karatsuba multiplikacji dużych liczb z operandami wejściowymi o nierównym rozmiarze i którego rozmiar nie jest potęgą 2, a może nawet nieparzystą liczbą ? Wyparowanie operandów oznacza dodatkową pamięć i chcę sprawić, że będzie ona wydajna.Mnożenie Karatsuba dla nierównych rozmiarów, operatory bez mocy.

Jedną z rzeczy, które zauważyłem w rozmiarze nierównomiernym Karatsuba jest to, że jeśli spróbujemy podzielić liczbę na "połówki" tak blisko, jak to możliwe, jedna połowa będzie miała elementy m + 1, a druga m , gdzie m = piętro (n/2), gdzie n oznacza liczbę elementów w podzielonym numerze. Jeśli obie liczby mają ten sam rozmiar nieparzysty, musimy obliczyć produkty o dwóch liczbach o rozmiarze m + 1, wymagające przechowywania n + 1, w przeciwieństwie do n, w przypadku, gdy n jest parzyste. Czy mam rację, zgadując, że Karatsuba dla dziwnych rozmiarów może wymagać nieco więcej pamięci niż dla nawet rozmiarów?

Źródło

2013-05-12 The_Sympathizer

[To wcześniejsze pytanie WSTĘPNE] (http://stackoverflow.com/questions/2187123/optimizing-karatsuba-implementation) dostarcza pewnych szczegółów dotyczących implementacji, które mogą pomóc –

W większości przypadków długość argumentów nie będzie potęgą 2. Myślę, że to rzadki przypadek. W większości przypadków będą różne długości operandów. Ale nie będzie to problemem dla Karatsuba algo.

Właściwie nie widzę tutaj żadnego problemu. To obciążenie (nieparzysta długość) jest tak lekkie i zdecydowanie nie jest wielka sprawa. Problemem o różnych długościach - załóżmy, że X = 1234 i Y = 45

więc, a = 12, b = 34, C = 0, d = 45 Tak więc, po tym X * Y = 10^4 * ac + 10^2 (ad + bc) + bd

ac = 0; 
bd = 34 * 45; 
ad + bc = (a + b) * (c + d) - ac - bd = 540;

A jeśli przyjmiemy, że możemy łatwo pomnożyć liczby dwucyfrowe - można uzyskać odpowiedź = 55530. To samo, co po prostu pomnóż 1234 * 45 w dowolnym kalkulatorze :) Tak więc, nie widzę problemu z pamięcią o różnych długościach liczby.

Źródło

2013-08-12 08:41:14 Mysterion

, jeśli x = 123, to w jaki sposób można podzielić liczbę na dwie części ? – Mastan

a = 1, b = 23, chyba. – Mysterion

Nop ,, Myślę, że ten algorytm nie zadziała, jeśli n bit jest liczbą nieparzystą – Mastan

Aby odpowiedzieć na wątpliwości w komentarzach powyżej. Sztuczka polega na zastosowaniu wzoru do obliczania mocy 10 w przypadku obliczeń dziesiętnych.

10^2m(A.C) + 10^m((A+B).(C+D)-A.C-B.D) + B.D 

m = n/2 + n%2 

n is length of number

Odwołaj się do strony wiki, która wyjaśnia szczegółowo.

Źródło

2017-01-26 02:49:58 pratikpawar

Mnożenie Karatsuba dla nierównych rozmiarów, operatory bez mocy.

Odpowiedz

Powiązane problemy