大数的乘法和比较

Question

我有这个问题：有 N 个数字（32 位）的 K 行。我必须选择数字乘积最大的那一行。

主要问题是 N 可以达到 20。我正在尝试用对数来做这个：

ld sum = 0, max = 0;
int index = 0;

for(int i = 0; i < k; i ++) { // K lines
    sum = 0, c = 0;
    for(int j = 0; j < n; j ++) { // N numbers
        cin >> t;
        if(t < 0)
            c++; // If the number is less than 0 i memorize it

        if(t == 1 || t == -1) { // if numbers = 1 OR -1
            sum += 0.00000001; // Because log(1) = 0
            if(t == -1)
                c ++;
        }
        else if(t == 0) { // if some number is equal to zero then the sum is = 0
            sum = 0;
            break;
        }
        else {
            sum += log10(fabs(t));
        }
    }

    if(c % 2 == 1) // if c is odd than multiply by -1
        sum *= -1;

    if(sum >= max) { 
        max = sum;
        index = i;
    }
    if((sum - max) < eps) { // if sum is equal to max i'm also have to choose it
        max = sum;
        index = i;
    }
}
cout << index + 1 << endl;

该程序在 50% 的测试用例中有效。有没有办法优化我的代码？

Answer 1

我认为这行肯定是错误的：

if(c % 2 == 1) // if c is odd than multiply by -1
    sum *= -1;

如果您的产品在 [0,1] 范围内，那么它的对数将为负，这将使它为正。我认为你应该把它分开。

Answer 2

如果你想避免 bignum 库，你可以利用它，如果你将 b1 和 b2 位数字相乘，那么结果是 b1+b2 位长

所以只需将一行中所有乘数的位数加在一起

并比较

记住一些数组中的结果

int bits(DWORD p) // count how many bits is p DWORD is 32bit unsigned int
    {
    DWORD m=0x80000000; int b=32;
    for (;m;m>>=1,b--)
     if (p>=m) break;
    return b;
    }

index 按结果位数降序对行进行排序
如果排序后的第一个比特数也是最大值那么它所在的行就是答案
如果你有不止一个最大值（更多的行具有相同的比特数并且也是最大值）
- 只有这样你才需要将它们相乘

现在乘法

你知道应该一次乘以所有最大行数
每次所有子结果都被同一个素数整除
除以它们
这样，结果将被截断为更少的位数
所以它应该适合 64 位值
你应该检查 sqrt(max value) 以内的素数
当您的最大值为 32 位时，然后检查素数最多为 65536
所以你可以制作一个静态的 table 素数来检查以加快速度
检查大于实际子结果的素数也没有意义
如果您知道如何使用 Eratosthenes 筛网可以极大地加快速度
但是你需要在每次除法后跟踪索引偏移量并使用周期性筛选 tables 这有点复杂但可行
如果你不检查所有的素数，只检查几个选定的素数
那么结果还是可以溢出
所以你也应该处理它（抛出一些错误或其他东西）
或将所有子结果除以某个值，但这会使结果无效

另一种乘法

您还可以按值对乘数进行排序
并检查所有最大行中是否存在一些
如果是，则将它们更改为一个（或从列表中删除）
这可以与之前的方法结合使用

双数乘法

你可以自己做大数乘法
结果最大为20*32=640位
所以结果将是无符号整数数组（位宽 8,16,32 ...随便你喜欢）
您还可以将数字作为字符串处理
在此处查看如何计算 fast exact bignum square in C++
它还包含乘法方法
这里NTT based Schönhage-Strassen multiplication in C++
但是对于像你这样的小数字来说速度会慢一些
最后你需要比较结果
所以从 MSW 做 LSW 比较，哪条线有更大的数字是最大线
（MSW 是最重要的词，LSW 是最不重要的词）

Answer 3

在 t == -1 的情况下，将 c 递增两次。

大数的乘法和比较

Multiplying and comparing big numbers

c++

algorithm

optimization

biginteger