Mnożenie pisemne dwóch liczb

Ten temat być może tak średnio podchodzi pod algorytmy, ale nie miałem pomysłu na lepszą kategorię. Załóżmy, że mamy 2 liczby, 123 i 456, i chcemy je pomnożyć. Wynik to będzie:
1236
+
12350
+
123*400

Jak widać, trzeba przeiterować 3 razy, czyli długość "456" (zakładamy że 123 to liczba o dużej podstawie (10^9), każda z cyfr w tej liczbie mieści się w incie, więc da się ją liniowo przemnożyć. Drugi czynnik zaś, to pojedyncza cyfra, tyle że uzupełniona o parę zer). I tutaj pytanie: czy da się to zrobić w mniejszej ilości iteracji, niż n? (n == liczba cyfr drugiej liczby) Lub czy ogólnie można to jakoś przyspieszyć? Nie chodzi mi tutaj o algorytmy typu karatsuby czy FFT - implementuję właśnie karatsubę i muszę napisać również do tego celu mnożenie "zwykłe". Niestety program napisany za pomocą algorytmu powyżej, na sprawdzarce działa zbyt wolno, i jestem na 99% pewny że to właśnie to jest wąskim gardłem. Z góry dzięki za pomoc :)

ew input nim jest, bo jest nim prawie zawsze

To zadanie z serii tych, które nie koncentrują się na wejściu. Może by coś to poprawiło, ale nie sądzę aby dużo.

Profilerem sprawdziłeś, czy to, to?

Nie, mam po prostu skąd-inąd taką informację. Nie chcę mówić skąd ani dlaczego - to nie tego tyczy się temat. Bardzo bym prosił, aby się tego trzymać (tak wiem, to komentarz do postu, ale mimo wszystko) - pytanie było, czy da się ten algorytm jakoś zoptymalizować.

Jeśli odpowiedź brzmi "nie da się", to chciałbym to usłyszeć od osoby kompetentnej, a nie od jakiegoś niezalogowanego gimnazjalisty, oczywiście nie obrażając nikogo z forumowiczów.

111*800000
mnożysz 111*8=888
i dopisujesz 5 zer na wydruku w sposób cout<<111*8<<setfill('0')<<setw(5)<<""<<endl;
88800000

@_13th_Dragon,
Wiem o tym, nawet o tym wspomniałem:

Drugi czynnik zaś, to pojedyncza cyfra, tyle że uzupełniona o parę zer

Dużo czasu tracisz na konwersje tekstu na liczbę. Jak nie kręć a takie wczytywanie wygląda jak: liczba=liczba*10+KolejnyZnak-'0'; - wyeliminuj te mnożenia.

prawda, mam podobną linijkę. Nie rozumiem jednak tego stwierdzenia: (literówka?)

Jak nie kręć

Natomiast konwertować na liczbę muszę, jeśli chcę mieć liczby o podstawie 10^9. Ogólnie wzorowałem się na tym: http://main.edu.pl/pl/user.phtml?op=lesson&n=32&page=algorytmika
Widać tam, że jeżeli użyjemy

liczba operator* (liczba x, liczba y)

, to dla każdej cyfry y mnożymy ją przez x. Nie da się tego w jakiś sposób przyspieszyć?

jeżeli wiemy że y jest cyfrą to:

r=0;
if(y&1) r+=x;
if(y&2) r+=x<<1;
if(y&4) r+=x<<2;
if(y&8) r+=x<<3;

anonimowy napisał(a):

1236
+
12350
+
123*400

Jak widać, trzeba przeiterować 3 razy, czyli długość "456" (zakładamy że 123 to liczba o dużej podstawie (10^9), każda z cyfr w tej liczbie mieści się w incie, więc da się ją liniowo przemnożyć. Drugi czynnik zaś, to pojedyncza cyfra, tyle że uzupełniona o parę zer). I tutaj pytanie: czy da się to zrobić w mniejszej ilości iteracji, niż n? (n == liczba cyfr drugiej liczby)

skoro już i tak każesz komputerowi przeliczać z binarnego na dziesiętny i z powrotem to czemu nie kazać mu liczyć na system o innej podstawie
możesz to na przykład liczyć w systemie o podstawie 123 zamiast 10
wtedy masz

10*3W

i liczysz:

10W
+
1030

i już masz swój wynik 3W0 (czyli 56088 dziesiętnie)
masz tylko dwie iteracje ;)