4
$\begingroup$

Primorial number system is a number sytem that uses primorials which are defined as follows :

Let $p_1=2, p_2=3,p_3=5,p_4=7,p_5=11,...$ the primes. The sequence of primorials, noted $p_n\#$ is $$(p_n\#)_{n\geq 1}=(2,2.3=6,2.3.5=30,2.3.5.7=210,210.11=2310,...$$

For example, we write $15$ and $28$ as $$15=2\times 6+1\times 2+1=(2:1:1)$$ $$28=(4:2:0)$$

I'm trying to think with your help hopefully about a multiplication algorithm of positive integers written in Primorial number system(two steps 1 and 2).


1.- Calculate congruences modulo any prime number via this number system, is very easy : for example, any integer like $(\color{green}{...:1:2:5:2:1:6:9:1:1:}\color{red}{0:0:2:1:1})$ is such that $$(\color{green}{...:6:9:1:1:}\color{red}{0:0:2:1:1})\equiv \color{green}{0+}\color{red}{0\times1+0\times 8+2\times 6+1\times 2+1\times 1 }\equiv 4 (\mod 11) $$since $2310\equiv 0 , 210\equiv 1 , 30\equiv 8 ,6\equiv 6, 2\equiv 2, 1\equiv 1 (\mod 11)$

So, $$\begin{cases} (2:1:1)\equiv \color{blue}{1,0,0,1,4} \mod 2,3,5,7,11\\ \land \\ (4:2:0)\equiv \color{blue}{0,1,3,0,6} \mod 2,3,5,7,11 \end{cases}$$

I took small integers but the same method works for integers with $\color{green}{\text{several hundred digits}}$ in base two.

2.- My idea to multiply $(2:1:1)$ and $(4:2:0))$ is then to use Chinese Remainder theorem once we have realized that $$P:=(2:1:1)\times (4:2:0)<2310\color{red}{(*)}$$

We obtain $$P\equiv \color{blue}{0,0,0,0,2} \mod 2,3,5,7,11$$ Then $\exists k, P=210k \land 210k=2 \text{ in } \mathbb Z/11\mathbb Z \iff 1k=2 \iff k=2$ And finally $$\boxed {P=(2:1:1)\times (4:2:0)=(2:0:0:0:0)}$$


a. Is that correct ? In particular $\color{red}{(*)}$ should probably be clarified

b. Switching from primorial numeral to base ten or two is easy. $$P=(2:1:1)\times (4:2:0)\to 15\times 28=420 \to (2:0:0:0:0)$$

is a procedure which, at first glance, seems sufficient. Nevertheless, I think that the question arises as to whether this basic procedure is really sufficient, since I have mentioned $\color{green}{\text{several hundred digits}}$(A bit random I admit) and wondered whether we could not rather say several thousand or even more.


Edit: To partially reply to the comment by @Steven Clark, here is another example $P=ab$, with $a=(...:c:b:a:0:1:9:6:2:2:1)\equiv 1,2,2,1,8,3,11$ and $b=(...:\gamma:\beta:\alpha:0:3:4:4:0:1:1)\equiv 1,0,3,4,6,2,5\mod 2,3,5,7,11,13,17$.

$P=\color{blue}1+2k_0. 1+2k_0=0 \text{ in }Z/3\implies k_0=\color{blue}1+3k_1. P=1+2(1+3k_1)=3+6k_1. P=3+1k_1 \text{ in }Z/5\implies k_1=3+5k_2. P=\color{blue}1\times 1+\color{blue}1\times 2+\color{blue}3\times 6 +30k_2. P=0+2k_2 \text{ in }Z/7\implies k_2=2+7k_3. P=\color{blue}1\times 1+\color{blue}1\times 2+\color{blue}3\times 6 +\color{blue}2 \times 30+210k_3...$

So, $$P=(...:\color{blue}{2:3:1:1})$$ (example constructed with $4\,397\times 7\,893=34\,705\,521$)

$\endgroup$
10
  • 1
    $\begingroup$ Have you tried the multiplication method for random numbers with $100$ digits ? $\endgroup$ Commented Apr 7, 2024 at 8:23
  • $\begingroup$ I meant $100$ digits in the decimal expansion. $\endgroup$ Commented Apr 7, 2024 at 9:03
  • 1
    $\begingroup$ Your example $15 \cdot 28=420=2\, p_4\#$ seems rather artificially constructed, and I find your description rather hard to follow. Perhaps posting your Python code would help clarify your algorithm, but I fail to see why your two step algorithm would be any more efficient than simply converting back and forth between the primorial number system and base 2 or 10 representations as mentioned in b. $\endgroup$ Commented Apr 10, 2024 at 0:49
  • 1
    $\begingroup$ It seems to me you're not really multiplying in the primorial representation, rather for $a \cdot b=c$ your multiplication algorithm just adds extra steps to this simpler algorithm: 1) compute residues of $a$ and $b$ mod small primes; 2) multiply residues of $a$ and $b$ mod small primes together to determine residues of $c$ mod small primes; 3) use Chinese remainder theorem to determine $c$ from residues of $c$ mod small primes. $\endgroup$ Commented Apr 11, 2024 at 17:35
  • 1
    $\begingroup$ I don't understand the example in your edit. You indicate for $P=a \times b=4\,397 \times 7\,893=34\,705\,521$ the residue representation of $b=7\,893$ is $1, 0, 1, 4, 4, 6, 4$ whereas I get $1, 0, 3, 4, 6, 2, 5$. Also, what is your definition of $Z$ and what do you mean by $Z/3$? Is $Z/3$ the same thing as $(\bmod 3)$? $\endgroup$ Commented Apr 27, 2024 at 15:37

3 Answers 3

1
$\begingroup$

Your algorithm isn't clear to me from your description, so I'll give an algorithm and hopefully you can clarify if your algoritrhm is the same or how it differs.


Assuming

$$a=\sum\limits_{j=0}^A a_j\, p_j\#=\{a_0, a_1, ..., a_A\}\tag{1}$$

and

$$b=\sum\limits_{j=0}^B b_j\, p_j\#=\{b_0, b_1, ..., b_B\}\tag{2}$$

then I believe

$$c=a\times b=\sum\limits_{j=0}^A \left(a_j\, p_j\#\, \sum\limits_{k=0}^B b_k\, p_k\#\right)\tag{3}.$$


Formula (3) above gives a normal numerical result, but this can easily be converted back into the primorial representation

$$c=\sum\limits_{j=0}^C c_j\, p_j\#=\{c_0, c_1, ..., c_C\}\tag{4}$$

if desired.


Could you please give a more generic description of your algorithm for $a\times b$ where $a$ and $b$ are defined in formulas (1) and (2) above? Perhaps the simple case $\left\{a_0, a_1, a_2\right\} \times \left\{b_0, b_1, b_2\right\}$ would provide some clarification because in your numeric example I don't understand where/how you're getting your numbers or applying the Chinese remainder theorem.

$\endgroup$
8
  • $\begingroup$ @StéphaneJaouen You've given an example of some numerical calculations which are obscure to me, so please define your algorithm for $a \times b=c$ in terms of the primorial coefficients $a_n$ and $b_n$ where for example $a=\left\{a_0, a_1, a_2\right\}$ and $b=\left\{b_0, b_1, b_2\right\}$ are the primorial representations of $a$ and $b$ and the mod-prime congruence coefficients $A_{p_n}=a\, (\bmod p_n)$ and $B_{p_n}=b\, (\bmod p_n)$ where $a=\left\{A_2, A_3, A_5, A_7, A_{11}\right\}$ and $b=\left\{B_2, B_3, B_5, B_7, B_{11}\right\}$ are the mod-prime congruence representations of $a$ and $b$. $\endgroup$ Commented Apr 26, 2024 at 20:16
  • $\begingroup$ @StéphaneJaouen I understand how to calculate modular arithmetic, but I'm not sure I understand your point. In your example of calculating $4\, (\bmod 11)$ it seemed to me the first step was converting from the primorial representation to the normal numerical representation. $\endgroup$ Commented Apr 26, 2024 at 20:25
  • $\begingroup$ @StéphaneJaouen You just illustrated my point as $(2:1:1)=2\times 6+1\times 2+1\times 1=15$ is exactly the conversion I was talking about which leads to $15=4\, (\bmod 11)$. $\endgroup$ Commented Apr 26, 2024 at 20:34
  • $\begingroup$ @StéphaneJaouen I know how to get to the mod-prime congruence representations of $a$ and $b$ independent of the primorial representations of $a$ and $b$, but perhaps you're also performing conversions on intermediate results during your algorithm for calculating $c=a \times b$? $\endgroup$ Commented Apr 26, 2024 at 20:43
  • $\begingroup$ @StéphaneJaouen Are you're really multiplying in the mod-prime congruence representation instead of the primorial representation, and then converting to the primorial representation at the end? If so, what's the point of converting from the numerical representation to the primorial representation at the beginning and from the mod-prime congruence representation to the primorial representation at the end? $\endgroup$ Commented Apr 26, 2024 at 21:21
0
$\begingroup$

I managed to work out the algorithm and implemented it in python: these are exactly the same ideas I was thinking about in OP. I also discovered that the algorithm described for going from modular remainders to primoradic coefficients already existed: it is Harvey Garner's algorithm from 1959. I provide a copy of a page with a multiplication of 100 digits by 150 randomly generated digit. The program works without problems with 5000 coefficients. This is equivalent, for example, to manipulating numbers of $10\,000$ digits in decimal notation.


NOUVEAU CALCUL

Entrez le nombre de chiffres primoriels pour A(<5000): 100 Entrez le nombre de chiffres primoriels pour B(<5000): 150 Générer A aléatoirement? (o/n): o A généré aléatoirement: 181:163:349:259:403:98:244:159:234:66:143:344:425:71:210:124:123:320:268:111:65:199:179:283:311:82:130:26:10:23:237:326:84:214:170:199:113:237:275:64:76:96:92:174:113:103:42:146:3:113:198:12:44:135:111:97:115:30:71:71:89:71:91:104:33:13:101:92:77:108:54:26:12:85:16:65:61:76:13:19:50:56:16:52:46:8:15:10:35:20:16:1:2:8:10:10:3:0:0:0

Générer B aléatoirement? (o/n): o

B généré aléatoirement:

338:213:681:40:199:159:117:261:626:473:658:176:654:143:428:267:683:83:510:102:34:252:436:584:190:276:132:668:479:376:403:105:611:342:184:465:292:284:21:268:150:219:322:536:475:325:410:83:366:452:317:482:495:446:282:266:195:43:246:95:175:138:119:129:267:92:171:300:190:41:50:153:116:43:212:290:358:255:0:4:189:228:295:286:108:120:31:271:98:252:21:65:167:54:98:143:110:159:166:31:83:157:214:177:51:68:111:59:175:42:81:125:141:92:32:55:124:51:49:16:83:2:89:35:32:94:0:21:10:60:32:44:24:22:39:25:24:16:9:3:26:14:6:13:2:3:6:2:1:1

A en notation primorielle:

(181:163:349:259:403:98:244:159:234:66:143:344:425:71:210:124:123:320:268:111:65:199:179:283:311:82:130:26:10:23:237:326:84:214:170:199:113:237:275:64:76:96:92:174:113:103:42:146:3:113:198:12:44:135:111:97:115:30:71:71:89:71:91:104:33:13:101:92:77:108:54:26:12:85:16:65:61:76:13:19:50:56:16:52:46:8:15:10:35:20:16:1:2:8:10:10:3:0:0:0)

B en notation primorielle:

(338:213:681:40:199:159:117:261:626:473:658:176:654:143:428:267:683:83:510:102:34:252:436:584:190:276:132:668:479:376:403:105:611:342:184:465:292:284:21:268:150:219:322:536:475:325:410:83:366:452:317:482:495:446:282:266:195:43:246:95:175:138:119:129:267:92:171:300:190:41:50:153:116:43:212:290:358:255:0:4:189:228:295:286:108:120:31:271:98:252:21:65:167:54:98:143:110:159:166:31:83:157:214:177:51:68:111:59:175:42:81:125:141:92:32:55:124:51:49:16:83:2:89:35:32:94:0:21:10:60:32:44:24:22:39:25:24:16:9:3:26:14:6:13:2:3:6:2:1:1)

Profondeur estimée pour A×B: 250

Calcul des résidus pour A...

Calcul des résidus pour B...

Reconstruction de A×B avec l'algorithme de Garner...

Représentation NN de A×B: (0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:336:947:579:863:60:555:977:678:637:1023:879:116:710:202:479:680:1052:382:940:959:781:833:1107:132:294:1132:309:566:989:395:884:382:658:140:192:518:641:742:676:558:370:375:604:210:395:605:883:900:510:0:690:717:621:587:516:447:233:90:528:655:518:598:797:148:92:271:384:449:453:839:69:732:120:601:622:710:230:688:339:709:613:344:637:286:160:427:319:644:459:380:453:87:481:600:565:168:315:674:26:674:118:442:461:361:251:104:599:588:410:416:547:392:362:267:204:241:435:56:528:498:135:472:54:447:182:266:345:380:237:391:22:1:303:268:217:183:439:307:141:395:132:165:101:179:191:225:206:189:223:182:58:25:245:230:201:137:312:86:262:73:211:172:187:84:193:30:177:33:54:40:145:139:122:87:214:104:66:51:138:75:27:164:8:78:92:62:32:49:136:47:58:91:39:53:43:29:45:0:87:29:15:60:32:16:58:35:2:26:25:25:6:28:26:6:15:7:7:1:4:0:0:0)

$\endgroup$
5
  • 1
    $\begingroup$ I believe you're referring to Harvey L. Garner's paper The Residue Number System from 1959 PROCEEDINGS OF THE WESTERN JOINT COMPUTER CONFERENCE? Perhaps you could post your Python implementation? $\endgroup$ Commented Sep 2 at 16:01
  • $\begingroup$ I had not had access to this document: thank you for the link. $\endgroup$ Commented Sep 2 at 16:06
  • $\begingroup$ I can of course happily post the program, but it's a bit long. How can I do this? $\endgroup$ Commented Sep 2 at 16:09
  • $\begingroup$ I was originally thinking you could post it in your answer, but if it's overly long perhaps you could post a link to it on GitHub or Online Python. $\endgroup$ Commented Sep 2 at 16:49
  • $\begingroup$ Sorry : it is in French $\endgroup$ Commented Sep 2 at 16:56
0
$\begingroup$

At the invitation of @Steven Clark, I'm posting my code below.

 import math import random import sympy import sys import os from functools import lru_cache def generate_primes(n): """Génère les n premiers nombres premiers.""" return list(sympy.primerange(1, sympy.prime(n+1))) @lru_cache(maxsize=1) def get_primes(n): """Version avec cache pour éviter de régénérer les nombres premiers.""" return generate_primes(n) def primorial_to_decimal(digits, primes): """Convertit une représentation primorielle en décimal.""" if not digits: return 0 value = 0 for i in range(len(digits)-1, -1, -1): value = value * primes[i] + digits[i] return value def format_primorial_representation(digits): """Formate la représentation primorielle dans l'ordre classique.""" return ":".join(map(str, digits[::-1])) def format_large_number(number, max_digits=80): """Formate un grand nombre pour l'affichage en indiquant sa taille.""" num_str = str(number) num_digits = len(num_str) if num_digits <= max_digits: return num_str else: # Affiche les premiers et derniers chiffres avec indication de la taille first_part = num_str[:max_digits//2] last_part = num_str[-(max_digits//2):] return f"{first_part}...{last_part} [nombre de {num_digits} chiffres]" def compute_prof(primes, m, n): """Estime la profondeur nécessaire pour A×B sans utiliser de logarithmes.""" # Estimation conservative: la profondeur nécessaire est au plus m + n return min(m + n, len(primes)) def compute_residues(digits, primes, prof): """Calcule les résidus d'un nombre en notation primorielle modulo les nombres premiers.""" residues = [] for i in range(prof): p = primes[i] residue = 0 product = 1 for j in range(len(digits)): residue = (residue + digits[j] * product) % p product = (product * primes[j]) % p residues.append(residue) return residues def garner_algorithm(residues, primes, prof): """Algorithme de Garner pour reconstruire les chiffres primoriels à partir des résidus.""" if prof == 0: return [] digits = [0] * prof digits[0] = residues[0] for i in range(1, prof): p = primes[i] S = 0 M = 1 for j in range(i): S = (S + digits[j] * M) % p M = (M * primes[j]) % p inv_M = pow(M, -1, p) if M != 0 else 0 digits[i] = (residues[i] - S) * inv_M % p return digits def clear_screen(): """Efface l'écran de la console.""" os.system('cls' if os.name == 'nt' else 'clear') def main(): # Configuration initiale n_primes = 10000 primes = get_primes(n_primes) # Ajuster la limite d'affichage des grands entiers old_limit = sys.get_int_max_str_digits() sys.set_int_max_str_digits(1000000) clear_screen() print("PROGRAMME DE CALCUL EN NOTATION PRIMORIELLE (NN)") print("================================================") print(f"Génération de {n_primes} nombres premiers...") print("Prêts pour les calculs.\n") while True: try: # Demander si l'utilisateur veut faire un nouvel essai choice = input("\nVoulez-vous faire un nouveau calcul? (o/n): ") if choice.lower() != 'o': print("Au revoir!") break clear_screen() print("NOUVEAU CALCUL") print("==============") # Demander les tailles de A et B m = int(input("Entrez le nombre de chiffres primoriels pour A(<5000): ")) n = int(input("Entrez le nombre de chiffres primoriels pour B(<5000): ")) # Avertissement pour les grandes tailles if m > 2000 or n > 2000: print("\n⚠️ Attention: les grandes tailles peuvent entraîner des temps de calcul longs.") confirm = input("Voulez-vous vraiment continuer? (o/n): ") if confirm.lower() != 'o': continue # Vérifier que m et n ne dépassent pas n_primes if m > n_primes or n > n_primes: print(f"Erreur: La taille ne peut pas dépasser {n_primes}.") continue # Génération des coefficients de A choice_A = input("Générer A aléatoirement? (o/n): ") if choice_A.lower() == 'o': digits_A = [random.randint(0, primes[i]-1) for i in range(m)] print(f"A généré aléatoirement: {format_primorial_representation(digits_A)}") else: digits_A = [] for i in range(m): while True: try: digit = int(input(f"Entrez le chiffre pour le nombre premier {primes[i]} (0-{primes[i]-1}): ")) if 0 <= digit < primes[i]: digits_A.append(digit) break else: print(f"Le chiffre doit être entre 0 et {primes[i]-1}.") except ValueError: print("Veuillez entrer un entier valide.") # Génération des coefficients de B choice_B = input("Générer B aléatoirement? (o/n): ") if choice_B.lower() == 'o': digits_B = [random.randint(0, primes[i]-1) for i in range(n)] print(f"B généré aléatoirement: {format_primorial_representation(digits_B)}") else: digits_B = [] for i in range(n): while True: try: digit = int(input(f"Entrez le chiffre pour le nombre premier {primes[i]} (0-{primes[i]-1}): ")) if 0 <= digit < primes[i]: digits_B.append(digit) break else: print(f"Le chiffre doit être entre 0 et {primes[i]-1}.") except ValueError: print("Veuillez entrer un entier valide.") print(f"\nA en notation primorielle: ({format_primorial_representation(digits_A)})") print(f"B en notation primorielle: ({format_primorial_representation(digits_B)})") # Estimation de la profondeur nécessaire pour AB prof = compute_prof(primes, m, n) print(f"Profondeur estimée pour A×B: {prof}") if prof > n_primes: print(f"Erreur: Le produit est trop grand pour {n_primes} nombres premiers.") continue # Calcul des résidus print("Calcul des résidus pour A...") residues_A = compute_residues(digits_A, primes, prof) print("Calcul des résidus pour B...") residues_B = compute_residues(digits_B, primes, prof) residues_AB = [(residues_A[i] * residues_B[i]) % primes[i] for i in range(prof)] # Reconstruction de A×B en notation primorielle print("Reconstruction de A×B avec l'algorithme de Garner...") digits_AB = garner_algorithm(residues_AB, primes, prof) # Affichage du résultat print(f"\nReprésentation NN de A×B: ({format_primorial_representation(digits_AB)})") # Vérification optionnelle en notation décimale verify = input("\nVoulez-vous vérifier en notation décimale? (o/n): ") if verify.lower() == 'o': try: print("Conversion de A en décimal...") A_dec = primorial_to_decimal(digits_A, primes) print("Conversion de B en décimal...") B_dec = primorial_to_decimal(digits_B, primes) print("Conversion de A×B en décimal...") AB_dec = primorial_to_decimal(digits_AB, primes) print("\n" + "="*50) print("VÉRIFICATION EN NOTATION DÉCIMALE") print("="*50) print(f"A = {format_large_number(A_dec)}") print(f"B = {format_large_number(B_dec)}") print(f"A×B = {format_large_number(AB_dec)}") # Vérification de l'exactitude du calcul is_correct = (A_dec * B_dec == AB_dec) print(f"Vérification: A×B = {is_correct}") if not is_correct: print("Attention: Il y a une divergence dans les calculs!") # Option de sauvegarde complète if len(str(AB_dec)) > 100: save = input("\nVoulez-vous sauvegarder le résultat complet dans un fichier? (o/n): ") if save.lower() == 'o': with open("resultat_complet.txt", "w") as f: f.write(f"A = {A_dec}\n\n") f.write(f"B = {B_dec}\n\n") f.write(f"A×B = {AB_dec}\n") print("Résultat sauvegardé dans 'resultat_complet.txt'") except Exception as e: print(f"Erreur lors de la vérification décimale: {e}") print("La vérification n'est pas possible pour ces grandes valeurs.") except ValueError: print("Veuillez entrer des valeurs valides.") except KeyboardInterrupt: print("\nAu revoir!") break except Exception as e: print(f"Une erreur inattendue s'est produite: {e}") # Restaurer la limite originale sys.set_int_max_str_digits(old_limit) if __name__ == "__main__": main() ''' 
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.