Преобразование двоичного в троичное представление

Вы можете использовать некоторые умные сокращения для преобразования. Следующий код является «неправильным» направлением, это преобразование из троичной системы в двоичную, основанное на том факте, что 3 ^ 2 = 2 ^ 3 + 1 с использованием только двоичного сложения. В основном я конвертирую две троичные цифры в три двоичных цифры. От двоичного к троичному было бы немного сложнее, так как потребовалось бы троичное сложение (и, возможно, вычитание) (работа над этим). Я предполагаю, что младшая значащая цифра находится в начале списка (это единственный способ, который имеет смысл), поэтому вам нужно читать числа «назад».

addB :: BNumber → BNumber → BNumber
addB a [] = a
addB [] b = b
addB (B0:as) (B0:bs) = B0 : (addB as bs) 
addB (B0:as) (B1:bs) = B1 : (addB as bs)
addB (B1:as) (B0:bs) = B1 : (addB as bs)
addB (B1:as) (B1:bs) = B0 : (addB (addB as bs) [B1])

t2b :: TNumber → BNumber
t2b [] = []
t2b [T0] = [B0]
t2b [T1] = [B1]
t2b [T2] = [B0,B1]
t2b (T2:T2:ts) = let bs = t2b ts in addB bs (B0:B0:B0:(addB bs [B1]))
t2b (t0:t1:ts) = 
   let bs = t2b ts
       (b0,b1,b2) = conv t0 t1
   in addB bs (b0:b1:b2:bs) 
   where conv T0 T0 = (B0,B0,B0)
         conv T1 T0 = (B1,B0,B0)
         conv T2 T0 = (B0,B1,B0)
         conv T0 T1 = (B1,B1,B0)
         conv T1 T1 = (B0,B0,B1)
         conv T2 T1 = (B1,B0,B1)
         conv T0 T2 = (B0,B1,B1)
         conv T1 T2 = (B1,B1,B1)

[Изменить] Вот двоичное направление в троичное, как и ожидалось, немного более длинное:

addT :: TNumber → TNumber → TNumber
addT a [] = a
addT [] b = b
addT (T0:as) (T0:bs) = T0 : (addT as bs) 
addT (T1:as) (T0:bs) = T1 : (addT as bs)
addT (T2:as) (T0:bs) = T2 : (addT as bs)
addT (T0:as) (T1:bs) = T1 : (addT as bs) 
addT (T1:as) (T1:bs) = T2 : (addT as bs)
addT (T2:as) (T1:bs) = T0 : (addT (addT as bs) [T1])
addT (T0:as) (T2:bs) = T2 : (addT as bs)
addT (T1:as) (T2:bs) = T0 : (addT (addT as bs) [T1])
addT (T2:as) (T2:bs) = T1 : (addT (addT as bs) [T1])

subT :: TNumber → TNumber → TNumber
subT a [] = a
subT [] b = error "negative numbers supported"
subT (T0:as) (T0:bs) = T0 : (subT as bs) 
subT (T1:as) (T0:bs) = T1 : (subT as bs)
subT (T2:as) (T0:bs) = T2 : (subT as bs)
subT (T0:as) (T1:bs) = T2 : (subT as (addT bs [T1])) 
subT (T1:as) (T1:bs) = T0 : (subT as bs)
subT (T2:as) (T1:bs) = T1 : (subT as bs)
subT (T0:as) (T2:bs) = T1 : (subT as (addT bs [T1]))
subT (T1:as) (T2:bs) = T2 : (subT as (addT bs [T1]))
subT (T2:as) (T2:bs) = T0 : (subT as bs)

b2t :: BNumber → TNumber
b2t [] = []
b2t [B0] = [T0]
b2t [B1] = [T1]
b2t [B0,B1] = [T2]
b2t [B1,B1] = [T0,T1]
b2t (b0:b1:b2:bs) = 
   let ts = b2t bs
       (t0,t1) = conv b0 b1 b2
   in subT (t0:t1:ts) ts
   where conv B0 B0 B0 = (T0,T0)
         conv B1 B0 B0 = (T1,T0)
         conv B0 B1 B0 = (T2,T0)
         conv B1 B1 B0 = (T0,T1)
         conv B0 B0 B1 = (T1,T1)
         conv B1 B0 B1 = (T2,T1)
         conv B0 B1 B1 = (T0,T2)
         conv B1 B1 B1 = (T1,T2)

[Edit2] Немного улучшенная версия subT, которая не нуждается в addT

subT :: TNumber →  TNumber →  TNumber
subT a [] = a
subT [] b = error "negative numbers supported"
subT (a:as) (b:bs) 
  | b ≡ T0 = a : (subT as bs)
  | a ≡ b =  T0 : (subT as bs)
  | a ≡ T2 ∧ b ≡ T1 =  T1 : (subT as bs)
  | otherwise = let td = if a ≡ T0 ∧ b ≡ T2 then T1 else T2 
                in td : (subT as $ addTDigit bs T1)  
    where addTDigit [] d = [d]
          addTDigit ts T0 =  ts
          addTDigit (T0:ts) d = d:ts 
          addTDigit (T1:ts) T1 = T2:ts
          addTDigit (t:ts) d = let td = if t ≡ T2 ∧ d ≡ T2 then T1 else T0
                               in td : (addTDigit ts T1)

Если вы делаете это с компьютером, все уже в двоичном формате, поэтому просто многократно делить на 3 и брать остатки примерно так же просто, как и все.

Если вы делаете это вручную, длинное деление в двоичном формате работает так же, как длинное деление в десятичном. просто раздели на три и возьми остатки. если мы начнем с 16

   ___101
11 |10000
     11
      100
       11
        1   

100000 / 11 = 101 + 1/11 so the least significnnt digit is 1

101/ 11 = 1 + 10/11  the next digit is 2

1  and the msd is 1

поэтому в троичном 121

Я думаю, что все упускают что-то важное. Во-первых, заранее вычислите таблицу, для каждого двоичного бита нам нужно представление в троичной форме. В MATLAB я построил это так, хотя каждый следующий шаг будет выполняться исключительно вручную, вычисления настолько просты.

dec2base(2.^(0:10),3)
ans =
0000001
0000002
0000011
0000022
0000121
0001012
0002101
0011202
0100111
0200222
1101221

Теперь рассмотрим двоичное число 011000101 (которое оказалось десятичным числом 197, как мы узнаем позже). Извлеките троичное представление для каждого двоичного бита из таблицы. Я выпишу соответствующие строки.

0000001 
0000011
0002101
0011202

Теперь просто суммируйте. Мы получаем это представление в троичном виде без переноса.

0013315

Да, это не троичные числа, но они почти соответствуют правильному представлению по основанию 3. Теперь все, что вам нужно сделать, это сделать керри. Начните с цифры единиц.

5 больше 2, поэтому вычтите число, кратное 3, и увеличьте вторую цифру результата соответствующим образом.

0013322

Вторая цифра теперь 2, допустимая троичная цифра, так что переходите к третьей цифре. Сделай это тоже,

0014022

Наконец, получив теперь полностью действительное троичное число...

0021022

Верны ли были мои расчеты? Я позволю MATLAB вынести за нас окончательное решение:

base2dec('011000101',2)
ans =
   197

base2dec('0021022',3)
ans =
   197

Указывал ли я, насколько тривиальной была эта операция, что я мог бы выполнить преобразование полностью вручную, по существу, непосредственно переходя от двоичного к троичному, по крайней мере, после того, как я записал и сохранил исходную таблицу?

Боюсь, я недостаточно знаю Haskell, чтобы выразить это в коде, но мне интересно, может ли использование правила Хорнера для вычисления многочленов дать метод.

Например, ax^2 + bx + c можно вычислить как c+x*(b+x*a).

Чтобы преобразовать, скажем, троичное число a*9+b*3+c в двоичное, нужно начать с двоичного представления a, затем умножить его на 3 (т. е. сдвинуть и добавить), затем добавить двоичное представление b, умножить результат на 3 и добавляет c.

Мне кажется, это должно быть выполнимо с картой (чтобы получить двоичное представление троичных цифр) и сгибом (из a, b -> a + 3 * b)

В случае, если это домашнее задание, псевдокод для записи x в базе b задом наперед:

while (x != 0) {
    q <-- x/b
    r <-- x - q*b
    print r
    x <-- q
}

Я уверен, что вы можете понять, как записать результат вперед, а не назад. Обратите внимание, что / должно быть целочисленным делением в стиле C (результатом является целое число, усеченное до нуля).

Обратите внимание, что это не зависит совсем от базы, в которой выполняется арифметика. Арифметика определяется целыми числами, а не представлением целых чисел в определенной базе.

Редактировать: Основываясь на вашем обновленном вопросе, я бы вставил цифровое представление в целое число (через or и сдвиги) и использовал алгоритм, описанный выше, с целочисленной арифметикой.

Конечно, вы могли бы сделать это, как вы описываете, но это похоже на очень много работы.

Я не думаю, что есть суперэффективный способ.

«Решение, которое я уже реализовал, состоит в том, чтобы сначала преобразовать число в десятичное число».

Я предполагаю, что вы на самом деле сначала конвертируете в какой-то встроенный целочисленный тип. Я не думаю, что встроенное целое имеет какое-либо отношение к основанию 10. (Хотя, когда вы его печатаете, будет преобразование основания 10).

Возможно, вы ожидаете, что будет какой-то алгоритм, который просматривает входные данные по одной цифре за раз и выдает результат.

Но, скажем, вы хотите преобразовать 3486784400 (по основанию 10) в основание 3. Вам нужно проверить каждую цифру перед выводом, потому что

3486784401 (base 10) = 100000000000000000000 (base 3)
3486784400 (base 10) =  22222222222222222222 (base 3)

..также

"вычислить результат, умножив числовые значения на соответствующую степень двойки"

явное вычисление мощности не требуется, см. преобразование из базы 60 в базу 10< /а>

Я думаю, что могут быть разные «взгляды» на проблему, хотя я не уверен, что какой-то из них быстрее или лучше. Например, младшая цифра n по основанию 3 — это просто n mod 3. Допустим, у вас уже есть двоичное представление n. Затем подумайте, как степени числа 2 работают по модулю 3. 2 ^ 0 = 1 по модулю 3, 2 ^ 1 = 2 по модулю 3, 2 ^ 2 = 1 по модулю 3, 2 ^ 3 = 2 по модулю 3, ... Другими словами , степени чередуются между 1 по модулю 3 и 2 по модулю 3. Теперь у вас есть простой способ получить младшую цифру по основанию 3 путем сканирования двоичного представления n и обычно только добавления 1 или 2 в каждой битовой позиции. где встречается 1.

Нет, вы не можете преобразовать число base2 в число base3, не загружая его в целое число. Причина в том, что числа 2 и 3 взаимно просты — у них нет общих делителей.

Если бы вы работали с основанием 2 и основанием 4 или даже с основанием 6 и основанием 9, то множество целых чисел до наименьшего общего кратного двух оснований было бы представлено двумя изоморфными множествами. Например, 13 (по основанию 4) = 0111 (по основанию 2), поэтому преобразование 1313 (по основанию 4) = 01110111 (по основанию 2) — это операция поиска и замены.

По крайней мере, решение, которое у вас есть, работает и относительно просто. Если вам нужно повысить производительность, преобразуйте все представление base2 в целое число, прежде чем начинать преобразование base3; это означает меньше операций по модулю. Альтернативой может быть обработка каждого символа в числе base2 один за другим, и в этом случае вы будете делить на все степени 3 для каждой цифры в представлении base2.

Если вы используете двоично-кодированный троичный код (одна пара битов на трит), вы можете преобразовать его с помощью параллельной арифметики. См. это руководство.