Conversion de base de nombre en tant qu'opération de flux

Question

Existe-t-il un dans l'espace de travail constant pour effectuer une taille arbitraire et des conversions de base arbitraires. C'est-à-dire, pour convertir une séquence de n nombres dans la plage [1,m] à une séquence de ceiling(n*log(m)/log(p)) nombres dans la plage [1,p] en utilisant un 1-à-1 mappage que (de préférence mais pas nécessairement) conservateurs ordre lexicographique et donne des résultats séquentiels?

Je suis particulièrement intéressé par les solutions qui sont viables en tant que fonction de tuyau, e.i. sont capables de gérer un plus grand ensemble de données que ce qui peut être stocké dans la RAM.

J'ai trouvé un certain nombre de solutions qui nécessitent un «espace de travail» proportionnel à la taille de l'entrée mais aucun qui puisse encore s'en sortir avec un «espace de travail» constant.

---

La suppression de la contrainte séquentielle peut-elle faire une différence? C'est: permettre lexicographique entrées séquentielles résultat en sorties non séquentielles lexicographique:

F(1,2,6,4,3,7,8) -> (5,6,3,2,1,3,5,2,4,3) 
F(1,2,6,4,3,7,9) -> (5,6,3,2,1,3,5,2,4,5) 

---

quelques réflexions:

pourrait ce travail?

StreamBase _n -> convert (n, lcm(n,p)) -> convert (lcm(n,p), p) -> StreamBase _p

(où lcm est plus petit commun multiple)

Answer 1

Je ne pense pas que ce soit possible dans le cas général. Si m est une puissance de p (ou vice versa), ou si elles sont les deux puissances d'une base commune, vous pouvez le faire, puisque chaque groupe de journal _m (p) est alors indépendant. Toutefois, dans le cas général, supposons que vous convertissez le nombre a1a2a3...an. Le nombre équivalent dans la base p est

sum(ai*mi-1 pour i dans 1..n)

Si nous avons traité les premiers i chiffres, nous avons la i e somme partielle. Pour calculer la somme « e partielle i+1, nous devons ajouter ai+1* mi.Dans le cas général, ce nombre va avoir des chiffres différents de zéro dans la plupart des endroits, nous aurons donc besoin de modifier tous les chiffres que nous avons traités jusqu'à présent. En d'autres termes, nous devrons traiter tous les des chiffres d'entrée avant de savoir ce que seront les chiffres de sortie finaux.

Dans le cas particulier où m sont les deux puissances d'une base commune, ou équivalente si journal _m (p) est un nombre rationnel, alors mi n'aura quelques chiffres non nuls dans la base p près de l'avant, de sorte que nous pouvons sortir en toute sécurité la plupart des chiffres que nous avons calculés jusqu'à présent.

Answer 2

Je pense qu'il y a une façon de faire la conversion en radix orientée flux dans l'ordre lexicographique. Cependant, ce que j'ai trouvé n'est pas suffisant pour le faire réellement, et il a quelques hypothèses:

1. La longueur des numéros de position est déjà connue.
2. Les nombres décrits sont des nombres entiers. Je n'ai pas considéré ce qui se passe avec les indices de maths et de -ive.

Nous avons une séquence de valeurs un de longueur p, où chaque valeur est dans l'intervalle [0, m -1]. Nous voulons une séquence de valeurs b de longueur q dans la plage [0, n -1]. Nous pouvons le k e chiffres de notre séquence de sortie b de un comme suit:

b _k = étage [somme (a _i * m ⁱ for i in 0 à p-1)/n k ] mod n

permet de réorganiser cette somme en deux parties, la divisant en un point arbitraire z

b _k = floor [(somme (a _i * m ⁱ pour i en z en p-1) + somme (a _i * m ⁱ for i in 0 à z-1 Supposons que nous ne connaissions pas encore les valeurs de a [0, z-1] et que nous ne puissions pas calculer le second terme de somme. Il nous reste à faire face à des gammes. Mais cela nous donne toujours des informations sur b _k.

La valeur minimale b _k peut être soit:

b _k> = floor [somme (a _i * m ⁱ pour i en z en p-1)/n ^k] mod n

et la valeur maximale b _k peut être soit:

b _k < = floor [(somme (a _i * m ⁱ pour i en z en p-1) + m ^z-1)/n ^k] mod n

Nous devrions être en mesure de faire un processus comme celui-ci:

1. Initialiser z être p. Nous allons compter à partir de p que nous recevons chaque caractère de un.
2. Initialiser k à l'indice de la valeur la plus significative dans b. Si mon cerveau fonctionne toujours, ce [log _n (m ^p)].
3. Lit une valeur de a. Décrémenter z.
4. Calculer la valeur min et max pour b _k.
5. Si les valeurs min et max sont les mêmes, entrez b _k et décrémentez k. Aller à 4. (Il est possible que nous avons déjà assez pour plusieurs valeurs consécutives de valeurs b _k)
6. Si z! = 0, alors nous nous attendons à plus de valeurs un. Goto 3.
7. J'espère que nous aurons terminé à ce stade.

Je n'ai pas considéré comment calculer efficacement les valeurs de plage encore, mais je suis raisonnablement confiant que calculer la somme des caractères entrants de un peut être fait beaucoup plus raisonnable que de stocker toutes un. Sans faire les maths cependant, je ne ferai pas de prétentions à ce sujet!

Answer 3

Oui, il est possible

Pour tous les caractères I (s) que vous lisez, vous allez écrire le caractère O (s) sur la base (journal de longueur * (In)/LOG (Out)) Plafond .

Allouer assez d'espace

Set x to 1 
Loop over digits from end to beginning # Horner's method 
    Set a to x * digit 
    Set t to O - 1 
    Loop while a > 0 and t >= 0 
     Set a to a + out digit 
     Set out digit at position t to a mod to base 
    Set a to a/to base 
Set x to x * from base 
Return converted digit(s) 

Ainsi, pour base 16 à 2 (qui est facile), en utilisant "192FE" nous lisons '1' et le convertir, puis répétez le '9', puis « 2 'et ainsi de suite en nous donnant' 0001 ',' 1001 ',' 0010 ',' 1111 'et' 1110 '. Notez que pour les bases qui ne sont pas des puissances communes, comme base 17 à base 2 signifierait lire 1 caractères et écrire 5.