14 stycznia 2019

Mnożenie większych liczb, alternatywne sposoby

Nie odkrywam tu nowych rzeczy, lecz podaję proste zastosowanie niektórych przekształceń stosowanych w innych przypadkach.

Równoczesne mnożenie kilku liczb.
Najlepiej, gdy mamy k czynników równej długości. Nie za dużo, ze względu na powstajace sumy, których liczność jest dana symbolem Newtona.
W ostateczności czynniki można uzupełniać zerami.
Zamieniamy iloczyny czynników na sumy iloczynów k cyfr. W pierwszym przybliżeniu są to wartości, które należy ostatecznie przenosić między pozycjami dziesiętnymi.
Jeśli mamy znaleźć wartość na pozycji i-tej, bierzemy iloczyn cyfry na pozycji i-tej dowolnego czynnika oraz cyfry jedności pozostałych. Podobnie robimy dla każdego czynnika i sumujemy. Następnie bierzemy cyfrę z pozycji (i-1) dowolnego czynnika oraz cyfrę dziesiątek dowolnego innego czynnika, Mnożymy przez siebie obie wraz z cyframi jedności pozostałych czynników. Sumujemy traktowane w ten sposób wszystkie permutacje czynników. Kontynuujemy szukanie permutacji, dopóki nie uzyskamy sum iloczynów najmniejszych możliwych czynników dla tej pozycji.

Przypomina to nieco czynności znane z Chińskiego Twierdzenia o resztach lub interpolacji wielomianami Lagrange'a. Można posłużyć się wzorem skróconego mnożenia (tu: szczególny przypadek luczb dwucyfrowych z cyfrą jedności 1):
(10a+1)(10b+1)(10c+1)(10d+1) =
10000abcd + 1000(abc+abd+acd+bcd)+100(ab+ac+ad+bc+bd+cd)+
10(a+b+c+d) + 1

Przykład: 64*27*21 = (6*2*2)*1000 + (6*2*1+6*2*7+2*2*4)*100  +(6*7*1+2*4*1+2*4*7)*10 + 4*7*1
Grupa przy 100 to suma cyfr z dwu dziesiątek, jednej jedności; przy 10 to suma iloczynów cyfr z dziesiątki i dwu jedności.
Sposób nadaje się, gdy jest kilka czynników równej długości. Później permutacje cyfr komplikują i spowalniają obliczenia.


Przerzucanie 11
Jest to metoda mnożenia egipskiego, chłopów rosyjskich zastosowana do 11 zamiast do 2.
Jeśli 11 dzieli b, to
a*b = (11a) * (11/b)
w przeciwnym przypadku wyłączamy resztę z dzielenia b przez 11.
Metoda jest posta, gdyż dzielenie liczby przez 11 sprowadza się do wypisywania cyfr uzyskanych przez różnicę cyfry z wcześniejszą.

Sposób pierwszy, wymaga poprawek: cyfry ilorazu to uzyskiwane cyfry na bieżącej pozycji:
np. 845130 / 11 =
8
4-8=-4
5-(-4)=9
1-9=-8
3-(-8)=11  = 0 ( mod 11) dodamy jedynkę na pozycji bardziej znaczącej
0-0 = 0
Na pozycjach cyfr mamy [8, -4, 9. -8, 11, 0] czyli liczbę 76830.

Sposób drugi, gdy cyfra mniej znacząca jest mniejsza od bieżącej, przenosimy jedynkę i wypisujemy cyfrę, zaś mniej znaczącą zastępujemy różnicą z otrzymaną:
845130 
8>4, 7; 75130
7>5, 6; 9130
9>1, 8; 330
3=3, 3; 00
0=0, 0
Iloraz 845130 / 11 = 76830.

Mnożenie przez 11 to suma dwu kolejnych cyfr na odpowiednich pozycjach:
7683*11 = [7, 7+6, 6+8, 8+3, 3], czyli 84513.

Sposób powoli zwiększa jedną liczbę kosztem zmniejszania drugiej.


Mnożenie dopełnieniami.
Mnożąc liczby a*b, szukamy najbliższej potęgi 10 lub polowy takiej potęgi przybliżajacej b, niech to będzie b=c*10^j+d
Wtedy
a*b = ac*10^j + a*d
Kontynuujemy rekursją dla a*d.
Przypominam, że w systemie dziesiętnym mnożenie przez 5 sprowadza się do dzielenia przez 2.
a*498 = a*(500-8) = (a/2)*1000 - 2a
a*507 = a*(5*101+2) = (100a+a)*10/2 + 2a
sposób znany i stosowany, choć nie wiem, jak często implementowany. Sprowadza wszystkie występujęce iloczyny do mnozenia lub dzielenia przez 2.

Brak komentarzy: