将浮点数的整数因子分解？

Question

我有一个困扰我的数学难题，它使我的大脑、白板和所有笔都崩溃了。我正在处理一个表达两个值的文件，一个是乘数，一个是百分比。这两个值都必须是整数。将这两个值相乘可以得到一个范围。范围是一个浮点值。

我的用户会编辑范围，我必须计算一个新的百分比和乘数值。还有疑惑吗？以下是一个例子：

    乘数：25000 苹果
    百分比：400（这相当于0.4%或0.004）
    范围：100.0 苹果（由乘数*百分比计算得出）

为了复杂化问题，百分比的允许值为0-100000。（意味着0-100%）乘数是介于1和32位int最大值之间的值（可能是无符号的）。

我需要允许用户输入范围，如下所示：

Range: .04 Apples

并计算出适当的百分比和乘数。以第一个例子为例：

    原始乘数：25000个苹果
    原始百分比：400（这相当于.4％或.004）
    原始范围：100.0个苹果（通过乘数*百分比计算）
    新范围：.01个苹果
    新百分比：40
    新乘数：25个苹果

这个例子的计算很容易，只需要按照新旧范围的比例因子将乘数和百分比调整即可。当用户更改值为1400.00555之类的值时，问题就出现了。突然间我没有一种简单的方法来调整这两个值。

我需要一种算法方法来获取产生最接近所需范围的M和P值。有什么建议吗？

- Phill

---

用户真的会输入像1400.00555这样的离谱值吗？还是这只是浮点数不精确的产物？在调整乘数和百分比以匹配新输入范围时，是否有任何规则？例如，如果范围现在为6，那么乘数为2和百分比为3是否重要，或者反过来呢？ - Eric J.

标题有些误导，因为您的百分比实际上不是整数，而是表示为整数的十进制值（可能是为了方便存储）。 - Matthew Scharley

尽管用户可能不会输入1400.00555，但我很容易看到他们输入类似于133.33333333333333333333333的内容。在乘数和百分比方面没有规定，只要范围正确即可。 在我的代码中，百分比被用作固定点数，但它表示为整数。 - Phill

你想做什么？为什么不能只存储“范围”？ - Pyrolistical

Answer 1

为了最大化存储小数点的数量，您应该使用1或0.1%的P。如果这导致M溢出，则增加P。

因此，对于您的示例1400.00555，P为1，M为1400006。

您的算法将搜索最低的P，使得M不会溢出。在这里，您可以进行二进制搜索。

public int binarySearch(int P0, int P1) {
   P = (P1 - P0)/2;
   if(P == P0) {
     if(R/(P0/100f) does not overflows 32-bit int) {
       return P0;
     } else {
       return P1;
     }
   }
   if(R/(P/100f) does not overflows 32-bit int) {
     return binarySearch(P0, P);
   } else {
     return binarSearch(P, P1);
   }
}

P = binarySearch(1, 100000);
M = round(R/(P/100f));

- Pyrolistical

---

这与我使用的解决方案非常接近。我尽可能地调整了P值并降低了M值，只是为了保持数值的可读性，但基本上我做了这个。 - Phill

Answer 2

从您的示例中我理解到，您可以用100000个不同的multiplicand * percentage来表示range。任何一个multiplicand的选择都会给您一个令人满意的百分比值，反之亦然。因此，您有了这个包含两个变量的方程：

Multiplicand * Percentage = 100.0

你需要找到另一个方程式（约束条件），以获得特定的乘数或百分比值来解决这个方程式。否则，您可以选择将百分比设为介于0-100000之间的任意数字，并将其代入第一个方程式中以获取乘数的值。我希望我正确理解了问题 :)

---

编辑：好的，那么你应该很容易地将范围进行因式分解。获取range，然后尝试通过将范围除以percentage(2-100000)来进行因式分解。一旦除法的余数为零，你就得到了因子。以下是一个快速的伪代码示例：

get range;
percentage = 2;
while(range % percentage != 0)
{
    percentage++;
}

multiplicand = range / percentage;

现在你需要做的就是计算你的限制：

max of percentage = 100000;
max of multiplicand = 4294967295;

Max of range = 4294967295 * 100000 = 429496729500000 (15-digit);

你的最大范围最多有15个数字。大多数编程语言中的double数据类型可以表示它。使用doubles进行计算，最后将Multiplicand & Percentage转换为int。

- Khaled Alshaya

---

你做了，我想。然而，我必须保证这两个值都是整数。例如，我不能假设百分比为50000，因为那可能会导致非整数的乘数。 - Phill

Answer 3

假设你有

1) M * P = A

然后你有了A的第二个值，因此M和P也有了新的值，我们称其为M2、P2和A2：

2) M2 * P2 = A2

我不确定这一点，但这似乎是你的意思：比率必须保持不变。

3) M/P = M2/P2

现在我们有3个方程和2个未知数M2和P2

---

解决方法之一：

3）变成

M/P = M2/P2
=>M2 = (M/P)*P2

将其替换为2）中的内容

(M/P)*P2*P2 = A2
=> P2*P2 = A2 * (P/M)
=> P2 = sqrt(A2 * (P/M))

首先解决P2，如果没有犯任何错误，再解决M2。

如果M2和P2必须是整数，则必须进行一些四舍五入。

编辑：我忘记了整数百分比，所以请注意。

P = percentage/100000 or P*100000 = percentage
P2 = percentage2/100000 or P2*100000 = percentage2

所以只需解决P2和M2，并将P2乘以100000

- Emile Vrijdags

---

很不幸，这并不能保证给我两个整数值 M2 和 P2。 - Phill

任意两个整数值都可以，只要它们是整数即可。 - Emile Vrijdags

如果你想要最接近的值，那么你最终会在某个时候将double解析为int以进行近似。 - Gordon Gustafson

Answer 4

（我之前有一个糟糕的方法，但是我把它删除了，因为它很糟糕。）

编辑：

肯定有比那更好的方法。让我们重新阐述问题：

你手头有一个任意浮点数。你想用两个整数来表示这个浮点数。当这两个整数相乘并除以100000.0时，结果等于这个浮点数。唯一的限制是其中一个整数必须小于或等于100000。

显然，你无法准确地表示浮点数。事实上，即使在“被乘数”中具有无限位的精度，你也只能准确地表示可表达为1/100000的数字。你可以用33333333作为一个数字，1作为另一个数字来准确地表示333.33333；你只是不能再得到更多的3。

考虑到这个限制，我认为你最好的选择是以下方法：

1. 将你的浮点数乘以100000，变成整数格式，可能是长整型或BigNumber的某个变体。 2. 因式分解它。记录所有因子。无论你将它们存储为2^3还是2*2*2或其他形式都无所谓。 3. 获取尽可能多的因子，而不会使它们全部相乘超过100000。这就成为你的百分数。（不要试图完美地做到这一点；找到最优解是一个NP难问题。） 4. 取剩下的因子并将它们相乘。这就是你的乘数。

- jprete

---

如果这是正确的问题陈述，那么只需将浮点数乘以100000，然后四舍五入的整数值就是乘数，百分比始终为1 :) - Emile Vrijdags

Answer 5

看起来你想选择M和P，使得R = (M * P) / 100000。因此M * P = 100000 * R，其中你必须将右侧舍入为整数。

我会将范围乘以100000，然后选择M和P作为结果的因子，以便它们不会超出允许的范围。

- starblue