Преобразование базы чисел с плавающей запятой без потери точности
Терминология
В этом вопросе я вызываю "число с плавающей запятой" "десятичное число", чтобы предотвратить неоднозначность с примитивными типами данных float/double Java. Термин "десятичный" не имеет отношения к "основанию 10".
Фон
Я выражаю десятичное число любой базы таким образом:
class Decimal{
int[] digits;
int exponent;
int base;
int signum;
}
который приблизительно выражает это значение double:
public double toDouble(){
if(signum == 0) return 0d;
double out = 0d;
for(int i = digits.length - 1, j = 0; i >= 0; i--, j++){
out += digits[i] * Math.pow(base, j + exponent);
}
return out * signum;
}
Я знаю, что некоторые преобразования невозможны. Например, преобразование 0.1 (base 3) в базу 10 невозможно, поскольку оно является повторяющимся десятичным. Точно так же преобразование 0.1 (base 9) в базу 3 невозможно, но возможно covnerting 0.3 (base 3). Вероятно, есть другие случаи, которые я не рассматривал.
Традиционный способ
Традиционный способ (вручную) изменения базы для целых чисел от основания 10 до основания 2 состоит в том, чтобы разделить число на показатели 2, а от основания 2 до основания 10 - умножить цифры на соответствующие показателями 2. Переход от основания x к основанию y обычно включает преобразование в основание 10 в качестве промежуточного элемента.
Первый вопрос: проверка аргумента
Поэтому мой первый вопрос заключается в том, что если я должен реализовать метод public Decimal Decimal.changeBase(int newBase), как я могу проверить, можно ли сделать newBase без повторения десятичных знаков (что несовместимо с конструкцией поля int[] digits, так как я не планирую создать поле int recurringOffset только для этого.
Второй вопрос: реализация
Следовательно, как это реализовать? Я инстинктивно чувствую, что этот вопрос намного легче решить, если первый вопрос будет решен.
Третий вопрос: как насчет вывода повторяющихся номеров:
Я не планирую создавать поле int recurringOffset только для этого.
Для будущих читателей этот вопрос также следует задать.
Например, согласно Wolfram | Alpha:
0.1 (base 4) = 0.[2...] (base 9)
Как это можно вычислить (вручную, если по программированию звучит слишком сложно)?
Я думаю, что такая структура данных, как это, может представлять это десятичное число:
class Decimal{
int[] constDigits;
int exponent;
int base;
int signum;
@Nullable @NonEmpty int[] appendRecurring;
}
Например, 61/55 может быть выражен следующим образом:
{
constDigits: [1, 1], // 11
exponent: -1, // 11e-1
base: 10,
signum: 1, // positive
appendRecurring: [0, 9]
}
Не вопрос о домашнем задании
Я не ищу никаких библиотек. Пожалуйста, не отвечайте на этот вопрос со ссылкой на любые библиотеки. (потому что я пишу этот класс просто для удовольствия, ОК?)
Ответы
Ответ 1
К вашему первому вопросу: всякий раз, когда основные факторы старой базы также входят в число основных факторов новой базы, вы всегда можете конвертировать, не становясь периодическими. Например, каждое базовое число 2 может быть представлено точно как основание 10. Это условие, к сожалению, является достаточным, но не необходимым, например, есть некоторые базовые 10 чисел, такие как 0,5, которые могут быть представлены точно как основание 2, хотя 2 не имеет простого коэффициента 5.
Когда вы записываете число как дробь и сводите его к младшим, он может быть представлен точно без периодической части в базе x тогда и только тогда, когда знаменатель имеет только простые множители, которые также появляются в x (игнорируя показатели простых чисел).
Например, если ваш номер равен 3/25, вы можете представить это точно в каждой базе, которая имеет основной коэффициент 5. Это 5, 10, 15, 20, 25,...
Если число равно 4/175, знаменатель имеет простые коэффициенты 5 и 7 и поэтому может быть представлен точно в основании 35, 70, 105, 140, 175,...
Для реализации вы можете либо работать на старой базе (в основном, делать дивизии), либо на новой базе (в основном делать умножения). Я бы избежал прохождения третьей базы во время преобразования.
Поскольку вы добавили периодические представления к своему вопросу, лучшим способом преобразования, по-видимому, является преобразование исходного представления в дробь (это всегда можно сделать и для периодических представлений), а затем преобразовать его в новое представление, выполнив разделение.
Ответ 2
Чтобы ответить на третью часть вопроса, как только вы уменьшите свою долю (и вы обнаружили, что "десятичное" расширение будет повторяющейся долей), вы можете обнаружить повторяющуюся часть, просто сделав длинное разделение и запоминание остатков, с которыми вы столкнулись.
Например, чтобы напечатать 2/11 в базе 6, вы выполните следующее:
2/11 = 0 (rem 2/11)
2*6/11 = 1 (rem 1/11)
1*6/11 = 0 (rem 6/11)
6*6/11 = 3 (rem 3/11)
3*6/11 = 1 (rem 7/11)
7*6/11 = 3 (rem 9/11)
9*6/11 = 4 (rem 10/11)
10*6/11 = 5 (rem 5/11)
5*6/11 = 2 (rem 8/11)
8*6/11 = 4 (rem 4/11)
4*6/11 = 2 (rem 2/11) <-- We've found a duplicate remainder
(Если бы 2/11 было конвертировано в базовое число 6 конечной длины, мы бы достигли 0 остатков вместо.)
Итак, ваш результат будет 0. [1031345242...]. Вы можете довольно легко создать структуру данных для ее хранения, учитывая, что до начала повторения может быть несколько цифр. Ваша предлагаемая структура данных хороша для этого.
Лично я, вероятно, просто работаю с фракциями, с плавающей точкой - это торговля с определенной точностью и точностью для компактности. Если вы не хотите идти на компромисс с точностью, с плавающей точкой будет много проблем. (Хотя с осторожным дизайном вы можете получить довольно далеко от него.)
Ответ 3
Я ждал этого после награды, потому что это не прямой ответ на ваши вопросы, а несколько советов, как подойти к вашей задаче.
-
Формат номера
Произвольная экспоненциальная форма числа при базовом преобразовании является большой проблемой. Вместо этого я бы преобразовал/нормализовал ваш номер в форму:
(sign) mantissa.repetition * base^exp
Где unsigned int exp - показатель наименьшей значащей цифры mantissa. mantissa,repetition может быть строкой для простой манипуляции и печати. Но это ограничило бы вашу максимальную базу грубого. Например, если вы зарезервируете e для экспоненты, вы можете использовать { 0,1,2,..9, A,B,C,...,Z } для цифр, поэтому максимальная база будет тогда только 36 (если не считать специальные символы). Если этого недостаточно, оставайтесь с цифровым представлением int.
-
Базовое преобразование (мантисса)
Я бы обработал мантисса как целое число. Таким образом, преобразование выполняется просто путем деления mantissa / new_base на арифметику old_base. Это можно сделать непосредственно на строках. С этим нет никаких проблем, так как мы всегда можем преобразовать любое целое число из любой базы в любую другую базу без каких-либо несоответствий, округления или остатков. Преобразование может выглядеть так:
// convert a=1024 [dec] -> c [bin]
AnsiString a="1024",b="2",c="",r="";
while (a!="0") { a=divide(r,a,b,10); c=r+c; }
// output c = "10000000000"
Где:
-
a - это номер в старой базе, который вы хотите преобразовать
-
b - новая база в старом базовом представлении
-
c - номер в новой базе
Используемая функция деления выглядит следующим образом:
//---------------------------------------------------------------------------
#define dig2chr(x) ((x<10)?char(x+'0'):char(x+'A'-10))
#define chr2dig(x) ((x>'9')?BYTE(x-'A'+10):BYTE(x-'0'))
//---------------------------------------------------------------------------
int compare( const AnsiString &a,const AnsiString &b); // compare a,b return { -1,0,+1 } -> { < , == , > }
AnsiString divide(AnsiString &r,const AnsiString &a, AnsiString &b,int base); // return a/b computed in base and r = a%b
//---------------------------------------------------------------------------
int compare(const AnsiString &a,const AnsiString &b)
{
if (a.Length()>b.Length()) return +1;
if (a.Length()<b.Length()) return -1;
for (int i=1;i<=a.Length();i++)
{
if (a[i]>b[i]) return +1;
if (a[i]<b[i]) return -1;
}
return 0;
}
//---------------------------------------------------------------------------
AnsiString divide(AnsiString &r,const AnsiString &a,AnsiString &b,int base)
{
int i,j,na,nb,e,sh,aa,bb,cy;
AnsiString d=""; r="";
// trivial cases
e=compare(a,b);
if (e< 0) { r=a; return "0"; }
if (e==0) { r="0"; return "1"; }
// shift b
for (sh=0;compare(a,b)>=0;sh++) b=b+"0";
if (compare(a,b)<0) { sh--; b=b.SetLength(b.Length()-1); }
// divide
for (r=a;sh>=0;sh--)
{
for (j=0;compare(r,b)>=0;j++)
{
// r-=b
na=r.Length();
nb=b.Length();
for (i=0,cy=0;i<nb;i++)
{
aa=chr2dig(r[na-i]);
bb=chr2dig(b[nb-i]);
aa-=bb+cy; cy=0;
while (aa<0) { aa+=base; cy++; }
r[na-i]=dig2chr(aa);
}
if (cy)
{
aa=chr2dig(r[na-i]);
aa-=cy;
r[na-i]=dig2chr(aa);
}
// leading zeros removal
while ((r.Length()>b.Length())&&(r[1]=='0')) r=r.SubString(2,r.Length()-1);
}
d+=dig2chr(j);
if (sh) b=b.SubString(1,b.Length()-1);
while ((r.Length()>b.Length())&&(r[1]=='0')) r=r.SubString(2,r.Length()-1);
}
return d;
}
//---------------------------------------------------------------------------
Он написан в С++ и VCL. AnsiString - это строковый тип VCL с самораспределяющими свойствами, а его члены индексируются из 1.
-
Базовое преобразование (повторение)
Есть два подхода к этому, о которых я знаю. Более простые, но с возможными круглыми ошибками устанавливают повторение на достаточно длинную последовательность строк и обрабатывают как дробное число. Например, rep="123" [dec], тогда преобразование в другую базу будет выполнено путем умножения на новую базу в старой базовой арифметике. Поэтому создадим достаточно длинную последовательность:
0 + 0.123123123123123 * 2
0 + 0.246246246246246 * 2
0 + 0.492492492492492 * 2
0 + 0.984984984984984 * 2
1 + 0.969969969969968 * 2
1 + 0.939939939939936 * 2
1 + 0.879879879879872 * 2 ...
------------------------------
= "0.0000111..." [bin]
С помощью этого шага вам необходимо выполнить повторный анализ и нормализовать число снова после шага коррекции экспоненты (в следующей броне).
Второй подход должен иметь повторения, хранящиеся как деление, поэтому вам нужно его в форме a/b в old_base. Вы просто конвертируете a, b в виде целых чисел (так же, как и мантисса), а затем выполняете деление для получения частичной части + части повторения.
Итак, теперь вам нужно преобразовать число в форму:
mantissa.fractional [new_base] * old_base^exp
или
mantissa.fractional+a/b [new_base] * old_base^exp
-
Базовое преобразование (экспонента)
Вам нужно изменить old_base^old_exp на new_base^new_exp. Самый простой способ - умножить число на значение old_base^old_exp в новой базовой арифметике. Итак, для начинающих умножьте все
mantissa.fractional+(a/b) [new_base]
на old_base old_exp раз в новой арифметике (позже вы можете изменить ее на мощность, возведя квадрат или лучше). И после этого нормализуйте свой номер. Итак, найдите, где начинается строка повторения, и ее позиция по отношению к . - это значение new_exp.
[Примечание]
Для этого вам понадобятся подпрограммы для преобразования old_base и new_base между собой, но поскольку база не является bignum, а просто простой небольшой unsigned int, вместо этого это не должно быть проблемой для вас (я надеюсь).
