Quel est le moyen le plus efficace de mettre en œuvre Karatsuba multiplication de grand nombre avec des opérandes d'entrée de taille inégale et Quelle taille n'est pas une puissance de 2 et peut-être même pas un nombre même? Rembourrage Les opérandes désignent une mémoire supplémentaire et je veux essayer de le faire mémoire -efficient.
Une des choses que je remarque dans la taille de nombre de nombres non uniformes Karatsuba est que si nous essayons de diviser le nombre en "moitiés" aussi près que possible de même que possible, une moitié aura des éléments M + 1 et l'autre m, où m = plancher (n / 2), n étant le nombre d'éléments du nombre de fractionnements. Si les deux chiffres sont de la même taille étrange, nous devons alors calculer des produits de deux nombres de taille M + 1, nécessitant un stockage N + 1, par opposition à N dans le cas où n est même. Ainsi, j'ai raison de deviner que Karatsuba pour des tailles impaires peut nécessiter un peu plus de mémoire que pour les tailles même?
3 Réponses :
La plupart du temps, la longueur des opérandes ne sera pas une puissance de 2. Je pense que c'est rare cas. La plupart du temps, il y aura différentes longueurs d'opérandes. Mais ce ne sera pas un problème pour un Karatsuba Algo.
En fait, je ne vois aucun problème ici. Cette surcharge (longueur étrange) est si légère et certainement pas une grosse affaire. Problème de différentes longueurs - supposons que x = 1234 et y = 45
donc, a = 12, b = 34, c = 0, d = 45
Donc, après que et, si nous Supposons que nous pourrions facilement multiplier des nombres à 2 chiffres facilement - vous pouvez obtenir la réponse = 55530. Même chose, comme il suffit de multiplier 1234 * 45 dans n'importe quelle calculatrice :) Donc, je ne peux donc voir aucun problème de mémoire avec différentes longueurs de chiffres. x * y = 10 ^ 4 * ac + 10 ^ 2 (ad + bc) + bd
Si x = 123, alors comment vous pouvez diviser le nombre en deux portions?
A = 1, b = 23, je suppose.
Nop , je pense que cet algorithme ne fonctionnera pas si n nombre de bits est un numéro de chiffres impairs
@Mastan pouvez-vous vérifier ma solution
Pour répondre à votre doute dans les commentaires ci-dessus. Truc est de suivre la formule pour calculer les pouvoirs de 10 en cas de calcul décimal. Voir Wiki Il explique en détail.
n est la longueur du nombre - dont 2 nombres multipliés?
Vous pouvez multiplier les chiffres par des pouvoirs de 10 afin que chacun d'entre eux aient même un nombre de chiffres. Appliquez l'algorithme de Karatsuba et ils divisent la réponse par le facteur de pouvoirs de 10 que vous avez multiplié les 2 numéros d'origine pour les rendre même.
EG: 123 * 12
Compute 1230 * 1200 et diviser la réponse avec 1000.
Cette question antérieure de la question fournit des détails de mise en œuvre qui pourrait aider