在不损失精度的情况下转换浮点数的基数

Question

术语

在这个问题中，我调用 "floating point number" "decimal number" 以防止与 float/double Java 原始数据类型产生歧义。术语 "decimal" 与 "base 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 是不可能的，但转换 0.3 (base 3) 是可能的。可能还有其他我没有考虑的情况。

传统方式

传统的（手工）换底方式，对于整数，从 10 进制到 2 进制，是将数字除以 2 的指数，从 2 进制到 10 是乘以数字由 2 的各自指数。从基数 x 更改为基数 y 通常涉及转换为基数 10 作为中间值。

第一题：参数验证

因此，我的第一个问题是，如果我要实现方法 public Decimal Decimal.changeBase(int newBase)，我如何验证是否可以在不导致循环小数（这与设计不兼容）的情况下进行 newBase int[] digits 字段，因为我不打算为此创建一个 int recurringOffset 字段。

第二题：实现

那么，如何实现呢？我本能地觉得如果第一个问题解决了，这个问题就容易解决了。

第三题：循环数输出怎么样：

I don't plan to make an int recurringOffset field just for this.

为了以后的读者，也应该问这个问题。

例如，根据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]
}

不是作业题

我不是在寻找任何图书馆。请不要参考任何库来回答这个问题。（因为我写这个 class 只是为了好玩，好吗？）

Answer 1

关于您的第一个问题：只要旧基数的质因数也在新基数的质因数中，您总是可以转换而不会变成周期性的。例如，每个以 2 为底数的数字都可以精确地表示为以 10 为底数。不幸的是，这个条件是充分的，但不是必需的，例如有一些以 10 为底数的数字，如 0.5，可以精确地表示为以 2 为底数，尽管 2 没有质因数5.

当您将数字写成分数并将其简化为最低项时，当且仅当分母仅具有也出现在 x 中的素数因子（忽略素数的指数).

例如，如果您的数字是 3/25，则您可以在每个素数为 5 的底数中准确表示它。即 5, 10, 15, 20, 25, ...

如果数字是 4/175，分母有质因数 5 和 7，因此可以精确地表示为 35、70、105、140、175，...

对于实现，您可以在旧基数（主要做除法）或新基数（主要做乘法）中工作。我会避免在转换过程中经过三垒。

由于您在问题中添加了周期性表示形式，因此最好的转换方式似乎是将原始表示形式转换为分数（这始终可以完成，对于周期性表示形式也是如此），然后将其转换为新的表示形式进行除法

Answer 2

要回答问题的第三部分，一旦你减少了你的分数（并且你发现 "decimal" 扩展将是一个循环分数），你可以通过简单地执行以下操作来检测循环部分手写除法并记住你遇到的余数。

例如，要以 6 为基数打印出 2/11，您可以这样做：

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...]。你可以很容易地设计一个数据结构来保存它，记住在循环开始之前可能有几个数字。您提出的数据结构对此很有帮助。

就我个人而言，我可能只使用分数，浮点数就是以一定的精度和准确度换取紧凑性。如果你不想在精度上妥协，浮点数会给你带来很多麻烦。（尽管经过精心设计，您可以走得更远。）

Answer 3

我在奖励后等待这个，因为这不是对您问题的直接回答，而是很少提示如何处理您的任务。

数字格式

基数转换过程中的任意指数形式的数字是个大问题。相反，我会 convert/normalize 你的号码形成：
```
(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;
    }
//---------------------------------------------------------------------------

它是用C++和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]
```
在这一步中，您需要进行重复分析并在指数校正步骤（下一个项目符号中）后再次对数字进行归一化。

第二种方法需要将重复存储为除法，因此您需要 old_base 中的 a/b 形式。您只需将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 而只是简单的小无符号整数，因此对您来说应该没有任何问题（我希望）。

在不损失精度的情况下转换浮点数的基数

Converting base of floating point number without losing precision

java

algorithm

math

base

decimal-point

术语

背景

传统方式

第一题：参数验证

第二题：实现

第三题：循环数输出怎么样：

不是作业题