Algorytm mnożenia

[Kera]

Poprzedni mój post wylądował w koszu , może ten nie wyląduje .
Kiedyś wymyśliłem inny sposób mnożenia, ale nie mam pojęcia czy jest znany czy nie, gdyż nigdzie w sieci nie znalazłem czegoś podobnego. Matematycy niech przymkną oko na mój opis, bo z pewnością przyprawi ich o ból głowy. Oto on:
Powiedzmy że chcemy pomnożyć dwie liczby 19-cyfrowe, grupujemy je na \(\displaystyle{ 5}\) równych części, począwszy od prawej strony do lewej, jeżeli ostatnia część zawiera mniej cyfr to dopisujemy zera na początku, np:
0123 4567 8910 1112 1314
\(\displaystyle{ \cdot }\)
0151 6171 8192 0212 2232
=
1871817045242859169563750742808452848

następnie podzielone w ten sposób liczby na grupy (4-cyfrowe) mnożymy od prawej do lewej strony. Wynik mnożenia grupujemy na dwie części, pierwsza (4-cyfrowa) od prawej do lewej strony jest częściowym wynikiem(na zielono), a drugą część wyniku dodajemy w następnym mnożeniu (na czerwono)
1314\(\displaystyle{ \cdot }\)2232 = 293 2848
1112\(\displaystyle{ \cdot }\)2232 + 1314\(\displaystyle{ \cdot}\)0212 + 293 = 276 0845
8910\(\displaystyle{ \cdot }\)2232 + 1112\(\displaystyle{ \cdot}\)0212 + 1314\(\displaystyle{ \cdot}\)8192 +276 = 3088 7428
4567\(\displaystyle{ \cdot}\)2232 + 8910\(\displaystyle{ \cdot}\)0212 + 1112\(\displaystyle{ \cdot}\)8192 + 1314 \(\displaystyle{ \cdot}\)6171 + 3088 = 2930 3750
0123 \(\displaystyle{ \cdot}\)2232 + 4567\(\displaystyle{ \cdot}\)0212 + 8910\(\displaystyle{ \cdot }\)8192 + 1112\(\displaystyle{ \cdot }\)6171 + 1314\(\displaystyle{ \cdot }\)0151 + 2930 = 8129 6956
0123\(\displaystyle{ \cdot }\)0212 + 4567\(\displaystyle{ \cdot }\)8192 + 8910\(\displaystyle{ \cdot }\)6171 + 1112\(\displaystyle{ }\)0151 + 8129 = 9259 8591
0123\(\displaystyle{ \cdot }\)8192 + 4567\(\displaystyle{ \cdot }\)6171 + 8910\(\displaystyle{ \cdot }\)0151+ 9259 = 3054 5242
0123\(\displaystyle{ \cdot }\)6171 + 4567\(\displaystyle{ \cdot }\)0151 + 3054 = 145 1704
0123\(\displaystyle{ \cdot }\)0151 + 145 =1 8718
jak przepiszemy zielone cyfry od ostatniego obliczenia do pierwszego powstanie wynik.
Co sądzicie o tym sposobie mnożenia???

[a4karo]

Coż, wymyśliłes sposób mnożenia pisemnego przy podstawie 10000.
Gdybyśmy mieli tyle palców, to pewnie tak właśnie byśmy to robili.

Metoda jest ok, tylko strasznie trudno opanować tabliczkę mnożenia, która ma 100000000 elementów

[Elayne]

Pomysł dzielenia czynników na mniejsze części nie jest nowy. Był znany w starożytności, współcześnie ma zastosowanie m.in. w algorytmach szybkiego mnożenia liczb całkowitych.

[Kera]

A czy implementując algorytm będzie on szybszy niż tradycyjne mnożenie??? Na architekturze procesorów x64 można liczbę podzielić na 9-cyfrowe bloki bez obawy że wynik będzie nieprawdziwy, co dla 27-cyfrowych liczb da tylko \(\displaystyle{ 9}\) mnożeń i \(\displaystyle{ 5}\) dodawań a w tradycyjnym \(\displaystyle{ 729}\) mnożeń i \(\displaystyle{ 365}\) dodawań, chyba że inaczej się to liczy?

[a4karo]

CO masz na myśli pisząc "tradycyjne mnożenie"? Komputery nie mnożą "pisemnie" - maja na to zupełnie inne algorytmy.

Jeżeli natomiast pragniesz zaimplementować działania dla bardzo duużych liczb, to z pewnością podział na dłuższe bloki będzie szybszy niż mnożenie "po cyferce" (patrz post Elayne)

[Elayne]

Odniosłem się tylko do kwestii dzielenia czynników na mniejsze części a nie do tego, jak i do czego te fragmenty czynników zostaną zastosowane. Zobacz np. na wiki opis algorytmu Karacuby: https://pl.wikipedia.org/wiki/Algorytm_Karacuby

[Kera]

dzięki za odpowiedzi, mimo że mój pomysł nie wnosi nic rewolucyjnego miło być autorem innego podejścia.

Dodano po 23 minutach 40 sekundach:
Miałby ktoś ochotę ten algorytm zaimplementować i wrzucić kod do mnożenia barrrrdzo dużych liczb?

[Borneq]

Trzeba by sprawdzić jak algorytm radzi sobie z liczbami większymi niż 64 bity. Do 64 bitów możemy użyć procesora, a jakie algorytmy używane są np. w GMP?

[Kera]

Borneq moim zdaniem algorytm działa doskonale, ograniczeniem na x64 jest podział mnożonych liczb na grupy max 9-cio cyfrowe. Np: najlepiej potraktować liczbę \(\displaystyle{ 100}\) cyfrową jako liczby 9-cio cyfrowe, powstanie w tedy \(\displaystyle{ 12}\) liczb 9-cio cyfrowych, a ich największa "reszta" przenoszona do następnego mnożenia nigdy nie przekroczy \(\displaystyle{ 2 ^{63} }\). Jedynym ograniczeniem jest czas i wielkość mnożonych liczb. Algorytm opracowałem wiele lat temu i byłbym szczerze zobowiązany poznać jego działanie w praktyce. Całkiem możliwe że można go jeszcze udoskonalić i przyspieszyć, a na pewno w przypadku podnoszenia liczb do kwadratu.

[Borneq]

Myślę że bez większych zmian można by zmienić z systemu dzieisętnego na dwójkowy i działałby na 32 bitowych liczbach. Tylko czy mnożenie w GMP nie używa już takiego algorytmu? Ten algoorytm ma złożoność kwadratową na kilkusetcyfrowych liczbach? W GMP jest używany jakiś, chyba podobny algorytm na mnożenie, ale dla większych liczb używa bardzo skomplikowanego bazującego na Szybkiej Transformacie Fouriera. Ten algorym wolno się "rozpędza", tak że dla kilkusetcyfrowych liczb jeszcze lepiej używa się tego prostszego, natomiast dla naprawdę wielkich liczb (wiele milionów cyfr rozwinięcia \(\displaystyle{ \pi}\)) używa się tego skomplikowanego.

[Kera]

Może jakieś pomysły udoskonalające algorytm?

[Kera]

Panie i Panowie, czy aby na pewno to dział "Dyskusje o matematyce"?
Ja nie jestem Matematykiem przez wielkie "M", nawet brak mi wiedzy w tym kierunku, dlatego się pytam czy widzicie możliwość optymalizacji tego algorytmu mnożenia. Mile widziana każda podpowiedź, choćby nawet niedorzeczna, bo te są czasami przełomowe.

[Dasio11]

Odpowiedź na to pytanie już padła: Algorytm Karacuby, Szybka Transformata Fouriera.

[Kera]

Przydał się komuś ten sposób mnożenia?
Zaimplementował go ktoś, jeśli tak to prosiłbym o podesłanie kodu lub działającego programu.

[Elayne]

To co pokazałeś to zwykłe mnożenie pisemne dwóch liczb z tą różnicą, że zamiast mnożyć pojedyncze cyfry liczb mnożymy grupy złożone z czterech cyfr [Analogia do rysunku poniżej]. Z czego, z jakiego powodu miało to być szybsze od tradycyjnego mnożenia?