转换浮点数的基数而不会丢失精度

Question

术语

在这个问题中,我称之为"浮点数""十进制数",以防止使用float/ doubleJava原始数据类型进行ambiguation .术语"十进制"与"基数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字段为了这.

第二个问题:实施

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

第三个问题:重复数字输出怎么样:

我不打算为此制作一个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]
}

---

不是作业问题

我不是在寻找任何图书馆.请不要参考任何图书馆回答这个问题.(因为我正在写这堂课只是为了好玩,好吗？)

Answer 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,......

为了实现,你可以在旧的基础(基本上做分区)或在新的基础(基本上做乘法)中工作.我会避免在转换期间通过第三个基地.

由于您在问题中添加了周期性表示,因此转换的最佳方式似乎是将原始表示转换为分数(这总是可以完成,也适用于周期性表示),然后通过执行除法将其转换为新表示.