523066680

用了两天 VS2015，不愧是宇宙最强编辑器（是我墨守成规，一直装在系统，从来不用）

s_minus 函数和 vec_minus 函数性能分析，1W位数，各调用2W次的分析结果：





可以看到涉及数组[]操作的语句消耗较高，采用高的进制(base)处理势在必行。

再聊聊《Modern Computer Arithmetic》（后面简称MCA）
对于64位平台 unsigned long long int 支持的最大数字是 2^64-1=18446744073709551615，20位，如果我们充分利用，使用2^64作为进制，或者10^19作为进制，
很容易会遇到溢出问题，MCA中给出了几种方案：
Let T be the number of different values taken by the data type representing the coefficients ai, bi. (Clearly, β ≤ T, but equality does not necessarily hold,
for example β = 10^9 and T = 2^32.) At step 3, the value of s can be as large as 2β − 1, which is not representable if β = T. Several workarounds
are possible:
either use a machine instruction that gives the possible carry of ai + bi,
or use the fact that, if a carry occurs in ai + bi, then the computed sum – if performed modulo T – equals t := ai +bi −T < ai; thus, comparing t and ai will determine if a carry occurred.
A third solution is to keep a bit in reserve, taking β ≤ T/2.

用 T 表示一个存储单元所能表示的数的量，则有 β <= T （这里 β 表示采用的进制，以及β不一定等于T，例如T=2^32，但采用的进制为10^9）。
考虑加法操作 s=a+b+d （d为1或0，是上一次加法补进的数值），s的最大可能值为 2*β-1，当 β = T 时该公式无法正确计算。考虑以下方案：
1. 内部编码实现 （水平有限，暂时这么翻译）
2. 通过-T取余数判断，t := a + b - T < a ，对比 t 和 a 断定是否进 1
3. 采用一个保守的进制数 β，令 β ≤ T/2.

523066680

回复 44# 老刘1号

      这个牛跌前面楼层有提到过呀。
我们主要在折腾大数字和浮点数。如果只在signed int范围内开整数根，早就可以结帖了。
小程说他要写一个版本的时候我以为“硬核”要来了，结果 ……
那本《MCA》非常硬核！打算用C艹实践其中一小部分算法（大部分看不懂，小部分似懂非懂）。

回复 43# SQYSQYSQY

批处理的“数组”属于伪数组，和其他语言的数组有本质的区别，因为批的“索引”不只是数字，还有字母和符号，变量长度亦不确定，这和其他语言的哈希表（hash table）相似。
在C/C++里面的数组操作不需要“搜索”，可直接通过计算偏移量取内存地址，因为定长的数组在初始化后占用一段连续内存空间，且每个单元占用相同字节，
给定一个编号，通过 编号*字节大小+起点地址 可得目标内存地址，直接存取。
C++ vector容器的 [] 操作符消耗占用高，和其独立的实现有关（可能做了各种判断和转换处理），换用更纯粹的C语言数组可以减少这种消耗。

实测，元素数量为80W的容器/数组，1000次遍历每一个元素并写入int值，

#include <iostream>
#include <vector>
#include <chrono>
using namespace std;
using namespace std::chrono;

const int SIZE = 800000;
void vec_test(void);
void c_array_test(void);
void c_pointer_test(void);
void time_used(system_clock::time_point& time_a);

vector<int> vec(SIZE);
int array1[SIZE];
int array2[SIZE];

int main(int argc, char *argv[])
{
    system_clock::time_point start = system_clock::now();
    for (int i = 0; i < 1000; i++) vec_test();
    time_used(start);

    for (int i = 0; i < 1000; i++)  c_array_test();
    time_used(start);

    for (int i = 0; i < 1000; i++)  c_pointer_test();
    time_used(start);
    return 0;
}

void vec_test(void) {
    register int it;
    for (it = 0; it < SIZE; it++) vec[it] = it;
}

void c_array_test(void) {
    register int it;
    for (it = 0; it < SIZE; it++) array1[it] = it;
}

void c_pointer_test(void) {
    register int it;
    register int *pt = array2;
    for (it = 0; it < SIZE; it++) *(pt + it) = it;
}

void time_used(system_clock::time_point& time_a) {
    duration<double> diff;
    diff = chrono::system_clock::now() - time_a;
    cout << "Time used: " << diff.count() << endl;
    time_a = chrono::system_clock::now();
}
复制代码

g++编译测试结果：
Time used: 1.24807
Time used: 0.400023
Time used: 0.393022

Visual Studio编译，差距更明显
Time used: 3.92722
Time used: 0.0410024
Time used: 0.0360021


如果一定要用 vector 又不想用它的 [] ，可以申请一个指针，int *vp = vec.data()
通过*vp指针直接算地址读写内存，速度和c_array一样快，想要更快，申请一个寄存器指针 register int *vp。
这就是自由度，可定制，可接管。

讨论算法，可以不分语言。谈论模块化思想，也可以不分语言，用批处理同样可以表达。
但要说极限压榨性能，怎么也轮不到批处理。

523066680

回复 48# 老刘1号


      这都是牛顿的功劳呀，牛迭是N次方，1/N次方都可以算，很多其他方程的根也可以算。因为他是在一个函数曲线任意一点(x)上求切线，然后这个切线不断迭代，向函数曲线和x轴的交点（根或者函数的解）逼近。
逼近速度非常快（差不多精度翻倍）。

现在回想，happy886r 当时写了好多大工程
happy886r - 数学计算工具 i 的重构版new i