Karatsuba moltiplicazione da dimensioni diverse, operandi senza motore-di-2

Question

Qual è il modo più efficiente per attuare Karatsuba gran moltiplicazione numero con operandi di ingresso di dimensioni diverse, con dimensioni che non è una potenza di 2 e forse neppure un numero pari ? Riempire gli operandi significa memoria aggiuntiva, e voglio provare a renderlo memoria -efficiente.

Una delle cose che noto in Karatsuba non in numero pari è che se proviamo a dividere il numero in "metà" il più vicino possibile, una metà avrà m + 1 elementi e l'altra m , dove m = floor (n/2), n è il numero di elementi nel numero split. Se entrambi i numeri hanno la stessa dimensione dispari, allora dobbiamo calcolare prodotti di due numeri di dimensione m + 1, richiedendo n + 1 memoria, invece di n nel caso in cui n è pari. Quindi ho ragione ad indovinare che Karatsuba per le dimensioni dispari potrebbe richiedere un po 'più di memoria rispetto alle dimensioni pari?

Answer 1

La maggior parte delle volte, la lunghezza degli operandi non sarà una potenza di 2. Penso che sia raro. La maggior parte delle volte ci saranno diverse lunghezze di operandi. Ma questo non sarà un problema per un algo Karatsuba.

In realtà, non vedo alcun problema qui. Questo overhead (lunghezza dispari) è così leggero e sicuramente non è un grosso problema. Problema circa lunghezze diverse - supponiamo che X = 1234 e Y = 45

Quindi, a = 12, b = 34, c = 0, d = 45 Così, dopo che X * Y = 10^4 * ac + 10^2 (ad + bc) + bd

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

e, se si assume, che potremmo moltiplicare 2 numeri a due cifre facilmente - si potrebbe ottenere la risposta = 55530. lo stesso, come solo si moltiplicano 1234 * 45 in qualsiasi calcolatrice :) Quindi, non vedo alcun problema di memoria con diverse lunghezze di numeri.

Answer 2

Per rispondere al tuo dubbio nei commenti sopra. Trucco è seguire la formula per calcolare le potenze di 10 in caso di calcolo decimale.

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 

Fare riferimento al wiki spiega in dettaglio.