Перевод из одной системы исчисления в другую. Как оказалось вопрос не тривиальный

[Zilon]

Стоит задача перевода значения из 2-ной системы исчисления в 4094-ичную (то есть (2^12 - 2) - ичную). То есть не кратную степени двойки. Существующие выкладки на эту тему предлагают значение числа в исходной сист. счисл. делить на основание. Проблема в том что исходное число в 2-ной системе может (и будет) n-битныйм. То есть произвольно большим.
Подскажите алгоритм решения этой задачи.
К стати эта задача возикла не из головы сумашедшего препода... мне ее завтра имплиментить)))

[Хыиуду]

http://www.uroki.net/docinf/docinf28.htm
В самом низу - деление в двоичной системе счисления.

[chur]

Для работы с большими числами надо использовать массивы. Этот вопрос регулярно появляется, на этом форуме тоже был. Попробуй поискать.

В твоей задаче лучше сначала создать массив массивов представляющий степени двойки в новой системе исчисления. Ну, конечно, надо ограничиться какой-то максимальной разрядностью входного двоичного числа

Код: Выделить всё

// пример создаваемого массива массивов
// bits[0] = [1];
// bits[1] = [2];
// bits[2] = [4];
// ....
// bits[12] = [2, 1];
// bits[13] = [4, 2];
// ...
newbase = 4094;
maxsize = 1024;
bits[] = [];

bits[0] = [1];
for i=1; i<maxsize; i++
  L = lenght(bits[i-1]);
  overflow = 0;
  for k=0; k<L; k++
    bits[i][k] = bits[i-1][k] * 2 + overflow;
    if bits[i][k] >= newbase 
      bits[i][k] -= newbase; overflow = 1;
    else 
      overflow = 0;
    end if
  end for
  if overflow then bits[i][L] = 1;
end for

Будем считать, что входное число представлено массивом "0" и "1". Если очередной разряд содержит "1", то просто по-разрядно прибавляем к результату соответствующий массив (из первого куска кода)

Код: Выделить всё

in = []; 
out = [];
for i=0; i<length(in); i++
  next unless in[i]
  for L=0; L<length(bits[i]); L++
    out[L] += bits[i][L]; 
  end for
end for

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