J'ai la calcul de la somme S = (A * x + b * y + c)% N. Oui, il ressemble à une équation quadratique, mais ce n'est pas parce que les X et Y ont des propriétés et doivent être calculés en utilisant des relations de récurrence. Parce que la somme dépasse même les limites de non signées longtemps longtemps, je veux savoir comment pourrais-je calculer cette somme en utilisant les propriétés de l'opération de modulo, propriétés qui permettent à l'écriture de la somme quelque chose comme ça (je dis quelque chose parce que je ne me souviens pas exactement Comment ces propriétés): (A * x)% n + (b * y)% n + c% n, évitant ainsi dépasser les limites de non signé longtemps longtemps.
Merci d'avance pour votre préoccupation! :)
6 Réponses :
Vous pouvez appliquer le module à chaque terme de la somme comme vous l'avez suggéré; Mais même après la somme, vous devez appliquer le module à nouveau pour obtenir votre résultat final.
Tu te souviens bien. L'équation que vous avez donnée, où vous% n tous les sommants sont corrects. Et ce serait exactement ce que j'utilise. Vous devriez aussi% n pour chaque somme partielle (et le total) à nouveau, car les résultats d'addition peuvent être encore supérieurs à N. mais que vous soyez prudent, cela ne fonctionne que si votre limite de taille est au moins deux fois plus grande que votre N. si ceci est Pas le cas, il peut devenir vraiment méchant.
BTW pour la notice suivante N Opérations des sommes partielles, vous n'avez pas à effectuer une division complète, une chèque> N et si plus grande juste une soustraction de n est suffisante.
Que diriez-vous de cela:
int x = (7 + 7 + 7) % 10; int y = (7 % 10 + 7 % 10 + 7 % 10) % 10;
Vous pouvez simplement déduire que si a% n = x code> signifie que pour certains entiers 0 et m code>: m * n + x = a code>. a% n = x code> et b% n = y code> alors p> (a * b) % N =
= ((m * N + x) * (l * N + y)) % N =
= ((m * l + x * l + m * y) * N + x * y) % N =
= (x * y) % N =
= ((a % N) * (b % N)) % N.
Mais vous pouvez même tirer le module dans le produit.
Excellent. Je soupçonnai mais je ne me suis pas souvenu que le module pouvait également être introduit dans les produits.
Vous pouvez prendre l'idée encore plus loin, si nécessaire:
S = ( (a%N)*(x%N)+(b%N)*(y%N)+c%N )%N
Vous pouvez non seulement réduire la variable MOD N avant de commencer le calcul, vous pouvez écrire votre propre MOD-MUL pour calculer A * X MOD N à l'aide d'une méthode Maj et ajoute et réduisez le résultat MOD N à chaque étape. . De cette façon, vos calculs intermédiaires ne nécessiteront qu'un bit de plus que n. Une fois ces produits calculés, vous pouvez les ajouter par paires et réduire le mod N après chaque addition qui ne nécessitera pas plus de 1 bit au-delà de la plage de n.
Il y a une implémentation de Python de la multiplication modulaire dans ma réponse à
pas complètement hors sujet, car le problème est contraint par les limites de taille des mots des langues ordinaires
Avez-vous juste essayé de la rompre dans cette forme avec un ensemble de données de test pour voir si elle fonctionne même (sans préciser pour déterminer si cela peut être fait de cette façon), parfois la chose la plus facile est de l'essayer, vous apprenez beaucoup de cette façon
Avez-vous considéré "s = (a x% n) + (b y% n) + (c% n)"? Plus spécifiquement, l'un de ces négatifs?
@Alnitak: Je suis d'accord. Mais désolé, je ne peux pas annuler le proches voix ...
HMM, si la somme dépasserait les limites, il est très probable qu'un terme dépasserait les limites. La somme au plus besoin que 2 bits plus d'espace que chaque terme.
Une autre solution consiste à utiliser une implémentation de la Bigint pour que vous n'ayez plus ce problème :-)