使用中语言实现整数的因子分解算法
中语言计算技术研究与发展联盟
舒生羽 wzyorg@gmail.com
中语言在GMP的基础上实现了对多精度计算的方便支持，因此使用中语言来编写数据值计算程序将是件简单而有效的事情。
下面的代码翻译自GMP库的factorize.c文件，为突显汉语在中语言里面的存在，全部符号都尽量采用汉字，并且为变量名字采用了便于阅读的选择。当然实际编程，这可能变得麻烦，但也许真正好的工作代码应该这样。个人有这样的经验，如果想将一段代码长期保留，并使得可复用和容易维护、理解，则使用纯中文的风格对于汉语言使用者而言是非常有利的。
这个程序是中语言及其编译器编译出的迄今为止最复杂的可执行程序，也是最实用的程序。由此，我们可以看到中语言及其编译器在编写复杂程序和构造大型软件上的能力。
完整代码如下：
/*使用中语言实现整数的因子分解算法.此程序翻译自gmp库的演示文件factorize.c.中语言计算技术研究与发展联盟 舒生羽 2012.12.13*//* Factoring with Pollard's rho method.Copyright 1995, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2005, 2009Free Software Foundation, Inc.This program is free software; you can redistribute it and/or modify it underthe terms of the GNU General Public License as published by the Free SoftwareFoundation; either version 3 of the License, or (at your option) any laterversion.This program is distributed in the hope that it will be useful, but WITHOUT ANYWARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR APARTICULAR PURPOSE. See the GNU General Public License for more details.You should have received a copy of the GNU General Public License along withthis program. If not, see http://www.gnu.org/licenses/. */来 朴库.标准库;来 朴库.标准进出;来 朴库.串;基{ 旗标_琐细: 元= 0; 平 增量: <向>-阵= {4, 2, 4, 2, 4, 6, 2, 6};}使用除数求因子: (测数: <太元>-牵* 败限: 向 元)->()={ 若(基.旗标_琐细 > 0) { 打印文套("[平凡除数 (%u)] ", 败限); 簿冲(基.标准出口); } 试因子: 向 目 元; 测数.扫一(0) -> 试因子; 试因子 ->>> 测数; 环(试因子) { 打印文套("2 "); 簿冲(基.标准出口); --试因子; } 商数, 余数: 太元; 环(阳) { 测数.截除(3, 商数, 余数); 若(余数 != 0) 跃; 商数 -> 测数; 打印文套("3 "); 簿冲(基.标准出口); } 环(阳) { 测数.截除(5, 商数, 余数); 若(余数 != 0) 跃; 商数 -> 测数; 打印文套("5 "); 簿冲(基.标准出口); } 7 -> 试因子; 失败次数: 向 元= 0; 增量阵位: 元= 0; 增量阵: <向>-址= 基.增量; 环(测数 != 1 -: [向 目]) { 测数.截除(试因子, 商数, 余数); 若(余数 != 0) { 增量阵[增量阵位] ->+ 试因子; 若(商数 < 试因子) 跃; 增量阵位 + 1 & 7 -> 增量阵位; 失败次数++; 若(失败次数 > 败限) 跃; } 否则 { 测数 <-> 商数; 打印文套("%lu ", 试因子); 簿冲(基.标准出口); 0 -> 失败次数; } }}使用步距为参数两倍的除数求因子: (测数: <太元>-牵* 上限: 向 元* 步参: 向 目)->()={ 若(基.旗标_琐细 > 0) { 打印文套("[平凡除数(%lu)] ", 上限); 簿冲(基.标准出口); } 余数: 太 元; 试除数: 太 元= (2 * 步参) -: [向 目]; 1 ->+ 试除数; 过([1 : 上限 - 1]) { 测数 % 试除数 -> 余数; 环(余数 == 0 -: [向 目]) { 试除数 ->/ 测数; 测数 % 试除数 -> 余数; //试除数.写出(基.标准出口, 10); 试除数.写出(); 簿冲(基.标准出口); 簿放入字(' ', 基.标准出口); } 2 * 步参 ->+ 试除数; }}使用pollard_rho法求因子: (测数: <太 元>-牵* 倍余增量: 向 目* 迭代幂: 向 目)->()={ 若(基.旗标_琐细 > 0) { 打印文套("[pollard-rho (%u)] ", 倍余增量); 簿冲(基.标准出口); } 公因子, 公因子临二: 太元; 同余者乙: 太元(2 -: [中 目]); 同余者甲: 太元(2 -: [中 目]); 同余者甲_伴: 太元(2 -: [中 目]); 差之倍: 太元(1 -: [向 目]); 绕数: 向 田= 1; 二之倍: 向 田= 1; 环(测数 != 1 -: [向 目]) { 环(阳) { 循 { 若(迭代幂 != 0) { 同余者甲.幂倍余(迭代幂, 测数, 同余者甲); 倍余增量 ->+ 同余者甲; } 否则 { 同余者甲 * 同余者甲 -> 公因子; 公因子 % 测数 -> 同余者甲; 倍余增量 ->+ 同余者甲; } 同余者甲_伴 - 同余者甲 -> 公因子; 差之倍 * 公因子 -> 公因子临二; 公因子临二 % 测数 -> 差之倍; 若(绕数 % 32 == 1) { 差之倍.共因(测数, 公因子); 若(公因子 != 1 -: [向 目]) 飞 因子已寻倒; 同余者甲 -> 同余者乙; } } 环(--绕数 != 0); 差之倍.共因(测数, 公因子); 若(公因子 != 1 -: [向 目]) 飞 因子已寻倒; 同余者甲 -> 同余者甲_伴; 二之倍 -> 绕数; 2 * 二之倍 -> 二之倍; 过([0 -: [向 田] : 绕数 - 1]) { 若(迭代幂 != 0) { 同余者甲.幂倍余(迭代幂, 测数, 同余者甲); 倍余增量 ->+ 同余者甲; } 否则 { 同余者甲 * 同余者甲 -> 公因子; 公因子 % 测数 -> 同余者甲; 倍余增量 ->+ 同余者甲; } } 同余者甲 -> 同余者乙; }-|因子已寻倒: 循 { 若(迭代幂 != 0) { 同余者乙.幂倍余(迭代幂, 测数, 同余者乙); 倍余增量 ->+ 同余者乙; } 否则 { 同余者乙 ->* 公因子; 公因子 % 测数 -> 同余者乙; 倍余增量 ->+ 同余者乙; } 同余者甲_伴 - 同余者乙 -> 公因子; 公因子.共因(测数, 公因子); } 环(公因子 == 1 -: [向 目]); // 在公因子被写掉之前, 除以公因子 测数.恰除(公因子, 测数); 若(!公因子.是否概率素(25)) { 循 { 随机增量: 太支; 太元::太数_随机(&随机增量, 1); 随机增量 -> 倍余增量; } 环(倍余增量 == 0); 若(基.旗标_琐细 > 0) { 打印文套("[复合因子--再次开始pollard-rho] "); 簿冲(基.标准出口); } 同(公因子, 倍余增量, 迭代幂); } 否则 { //公因子.写出(基.标准出口, 10); 公因子.写出(); 簿冲(基.标准出口); 簿放入字(' ', 基.标准出口); } 测数 ->% 同余者甲; 测数 ->% 同余者甲_伴; 测数 ->% 同余者乙; 若(测数.是否概率素(25)) { //测数.写出(基.标准出口, 10); 测数.写出(); 簿冲(基.标准出口); 簿放入字(' ', 基.标准出口); 跃; } }}因子分解: (测数: <太 元>-牵* 参数: 向 目)->()={ 除数上限: 向 元; 若(测数.方向() == 0) 归; // 根据测数的尺寸来设置平凡的除数限制. 测数.尺度(2) -> 除数上限; 若(除数上限 > 1000) 1000 * 1000 -> 除数上限; 否则 除数上限 * 除数上限 -> 除数上限; 若(参数 != 0) 使用步距为参数两倍的除数求因子(测数, 除数上限 / 10, 参数); 否则 使用除数求因子(测数, 除数上限); 若(测数 != 1 -: [向 目]) { 若(基.旗标_琐细 > 0) { 打印文套("[是素数吗?] "); 簿冲(基.标准出口); } 若(测数.是否概率素(25)) //测数.写出(基.标准出口, 10); 测数.写出(); 否则 使用pollard_rho法求因子(测数, 1$L, 参数); }}道: (道佐长: 元* 道佐组: <口>-址-阵)->(元)={ 参数: 向 目; 若(道佐长 > 1 && !串比较(道佐组[1], 1#"-v")) { 1 -> 基.旗标_琐细; 道佐组++; 道佐长--; } 若(道佐长 > 1 && !串比较(道佐组[1], 1#"-q")) { -1 -> 基.旗标_琐细; 道佐组++; 道佐长--; } 测数: 太 元; 若(道佐长 > 1) { 0 -> 参数; 过(阵索@[1 : 道佐长 - 1]) { 若(!串有长比较(道佐组[阵索], 1#"-Mp", 3)) { 字串变元(道佐组[阵索] + 3) -> 参数; 1 -: [向 目] -> 测数; 参数 -><< 测数; 1 ->- 测数; } 否则 若(!串有长比较(道佐组[阵索], 1#"-2kp", 4)) { 字串变元(道佐组[阵索] + 4) -> 参数; 复; } 否则 { 测数.获值(道佐组[阵索], 0); } 若(测数 == 0 -: [向 目]) 放入串(1#"-"); 否则 { 因子分解(测数, 参数); 放入串(1#""); } } } 否则 { 环(阳) { 测数.读进(基.标准入口, 0); 若(簿尾乎(基.标准入口)) 跃; 若(基.旗标_琐细 >= 0) { 测数.写出(基.标准出口, 10); 打印文套(" = "); } 因子分解(测数, 0); 放入串(1#""); } } 退出(0);}程序的执行结果如下：
官网文件参考:
http://www.zhongyuyan.org/ZStudy/超酷程序/分解整数.html