Как преобразовать поток битов в число base20? - PullRequest
Новая
       52

Как преобразовать поток битов в число base20?

0 голосов
/ 12 марта 2019

Дан битовый поток (непрерывная строка битов, слишком длинная, чтобы быть обработанной за один раз), и результатом должен быть совпадающий поток чисел base20.

Процесс прост для небольшого числа битов:

Предполагая, что самый старший бит прав: 

110010011 = decimal 403 (1 * 1 + 1 * 2 + 1 * 16 + 1 * 128 + 1 * 256)
403 / 20 = 20 R 3
20 / 20 = 1 R 0
1 / 20 = 0 R 1
Result is [3, 0, 1] = 3 * 1 + 0 * 20 + 1 * 400

Но что, если биты слишком велики, чтобы их можно было преобразовать в десятичное число за один шаг?

Мой подход заключался в выполнении обоих процессов в цикле: преобразование битов в десятичное и преобразование десятичного числа в числа base20. Этот процесс требует, чтобы при переходе по битам множители (значения положения) были понижены, потому что в противном случае они быстро увеличатся слишком сильно, чтобы их можно было рассчитать. 64-й бит умножился бы на 2 ^ 64 и т. Д.

1 Ответ

2 голосов
/ 12 марта 2019

примечание: Я понял вопрос о том, что поток битов поступает неизвестной длины и в течение неизвестной продолжительности, и необходимо выполнить преобразование в реальном времени из базы 2 в базу 20.

Я не верю, что это можно сделать за один раз. Проблема состоит в том, что база 20 и база 2 не имеют общего основания, а правила модульной арифметики не позволяют решить проблему чисто. 

(a+b) mod n = ( (a mod n) + (b mod n) ) mod n
(a*b) mod n = ( (a mod n) * (b mod n) ) mod n    
(a^m) mod n = ( (a mod n)^m ) mod n

Теперь, если у вас есть число A , записанное в базе p и q ( p ) как 

A = Sum[a[i] p^i, i=0->n] = Sum[b[i] q^i, i=0->n]

Тогда мы знаем, что b[0] = A mod q. Однако мы не знаем A и, следовательно, вышеизложенное говорит нам, что 

b[0] = A mod q = Sum[a[i] p^i, i=0->n] mod q
               = Sum[ (a[i] p^i) mod q, i=0->n] mod q
               = Sum[ ( (a[i] mod q) (p^i mod q) ) mod q, i=0->n] mod q

Это означает, что:

Если вы хотите узнать самую младшую цифру b 0 числа в базе q , вам необходимо знать полное число.

Это можно упростить, только если q = p m как 

b[0] = A mod q = Sum[a[i] p^i, i=0->n] mod q
               = Sum[ (a[i] p^i) mod q, i=0->n] mod q
               = Sum[ a[i] p^i, i=0->m-1]

Короче говоря, поскольку q = 20 и p = 2. Я должен сказать, no , это невозможно сделать за один проход. Кроме того, напомните себе, что я говорил только о первой цифре в базе q, но не о i-й цифре.

В качестве примера представим битовый поток 1000 × 0, за которым следует один 1. Это похоже на число 2 1000 . Первая цифра проста, но получить любую другую цифру ... вы, по сути, в довольно трудном положении.

...