用Forcal封装HugeCalc大数算法库

forcal

上面例子4的说明：

求10000000～20000000之间的素数，设c＝0，对每两个相邻的素数a、aa，循环计算：

    dd=[a*aa], cc=Pow(aa,50),
    c＝c+Pow(a,100)*(a+aa)*(a*aa%(a+b))+(c+cc)/dd

耗时81.813秒，结果为：

118 665 309 304 833 785 345 563 386 324 648 547 035 425 038 181 578 220 747 682 524 511 062 461 093 647 452 509 972 200 155 644 319 793 492 290 959 190 989 248 040 819 643 043 365 337 914 648 956 443 540 250 313 176 180 479 801 437 839 936 533 996 316 340 239 213 527 641 718 206 798 942 547 135 174 392 619 526 762 202 809 933 722 161 432 981 246 861 507 662 608 839 089 941 376 556 367 810 280 300 360 243 722 730 232 063 290 238 146 939 767 028 313 016 072 960 038 404 229 118 819 825 747 244 356 878 312 530 448 163 689 704 203 194 296 789 853 787 954 727 493 976 733 762 078 122 199 193 818 658 219 552 717 804 563 143 393 685 352 728 907 572 003 138 319 623 877 967 200 005 822 861 587 965 707 457 753 488 360 307 036 940 266 934 602 297 449 993 339 542 136 539 259 760 878 719 170 329 500 691 767 171 086 114 357 803 297 061 434 015 155 462 723 617 832 105 664 188 393 652 214 125 581 343 926 076 035 248 699 681 537 862 798 185 719 304 702 821 373 652 044 161 974 149 965 460 153 175 315 934

不知效率如何？结果是否正确？

forcal

例子4的C++相关代码片段（在FcHugeCalcCode.rar中的root函数内）：

1.         CHugeInt a,b,c,aa,cc,dd,ee;
   
2.         a=10000000; b=20000000; c=0;
   
3.         a.NextPrime(a); aa.NextPrime(a);
   
4.         while(aa<=b)
   
5.         {
   
6.                 dd=a*aa; cc.Pow(aa,50); ee.Pow(a,100);
   
7.                 c=c+ee*(a+aa)*(a*aa%(a+b))+(c+cc)/dd;
   
8.                 a=aa; aa.NextPrime(a);
   
9.         }

复制代码

借用函数名root，可在Forcal脚本中与C++比较执行结果和运行效率。以下虽是Forcal脚本，但root函数里却是执行的以上C++代码。

1. !using["HugeCalc"];
   
2. mvar:
   
3. t0=sys::clock();
   
4. i: printff["\r\n"], NewHC[HI].Root(10000000,20000000).Show().free[];
   
5. [sys::clock()-t0]/1000;

复制代码

运行结果与Forcal脚本相同，程序耗时如下：

Forcal耗时82.828秒，C++耗时81.297秒。

可以看出，C++运算符重载的效率快降到脚本水平了。C++运算符重载以执行效率的下降换来了代码的清晰。

forcal

又在FcHugeCalc中加了一个缓冲区，运行以下代码，C++已比Forcal慢了，当然这可能是比较特殊的情况吧。

1. !using["HugeCalc"];
   
2. mvar:
   
3. t0=sys::clock();
   
4. i: printff["\r\n"],
   
5.    a=NewHC[HI].SetNum[10000000].free[],
   
6.    b=NewHC[HI].SetNum[20000000].free[],
   
7.    c=NewHC[HI].SetNum[0].free[],
   
8.    aa=NewHC[HI].free[],
   
9.    i=0, a.NextPrime[a], aa.NextPrime[a],
   
10.    while{LE(aa,b),
    
11.      oo{
    
12.        dd=a*aa, cc=Pow(aa,50),
    
13.        c.Set[c+Pow(a,100)*(a+aa)*(a*aa%(a+b))+(c+cc)/dd]
    
14.      },
    
15.      a.Set[aa], aa.NextPrime[a],
    
16.      i++
    
17.    },
    
18.    c.Show(),
    
19.    i;
    
20. [sys::clock()-t0]/1000;
    
21. 
    
22. //以下root函数中的C++代码以运算符重载的方式执行与上面相同的计算
    
23. 
    
24. t0=sys::clock();
    
25. i: printff["\r\n"], HugeCalc::NewHC[HI].Root(10000000,20000000).Show().free[];
    
26. [sys::clock()-t0]/1000;

复制代码

结果（去掉了一些无用的输出，添加了些注释）：

118 665 309 304 833 785 345 563 386 324 648 547 035 425 038 181 578 220 747 682 524 511 062 461 093 647 452 509 972 200 155 644 319 793 492 290 959 190 989 248 040 819 643 043 365 337 914 648 956 443 540 250 313 176 180 479 801 437 839 936 533 996 316 340 239 213 527 641 718 206 798 942 547 135 174 392 619 526 762 202 809 933 722 161 432 981 246 861 507 662 608 839 089 941 376 556 367 810 280 300 360 243 722 730 232 063 290 238 146 939 767 028 313 016 072 960 038 404 229 118 819 825 747 244 356 878 312 530 448 163 689 704 203 194 296 789 853 787 954 727 493 976 733 762 078 122 199 193 818 658 219 552 717 804 563 143 393 685 352 728 907 572 003 138 319 623 877 967 200 005 822 861 587 965 707 457 753 488 360 307 036 940 266 934 602 297 449 993 339 542 136 539 259 760 878 719 170 329 500 691 767 171 086 114 357 803 297 061 434 015 155 462 723 617 832 105 664 188 393 652 214 125 581 343 926 076 035 248 699 681 537 862 798 185 719 304 702 821 373 652 044 161 974 149 965 460 153 175 315 934
76.937    //Forcal结果，耗时76.937秒

118 665 309 304 833 785 345 563 386 324 648 547 035 425 038 181 578 220 747 682 524 511 062 461 093 647 452 509 972 200 155 644 319 793 492 290 959 190 989 248 040 819 643 043 365 337 914 648 956 443 540 250 313 176 180 479 801 437 839 936 533 996 316 340 239 213 527 641 718 206 798 942 547 135 174 392 619 526 762 202 809 933 722 161 432 981 246 861 507 662 608 839 089 941 376 556 367 810 280 300 360 243 722 730 232 063 290 238 146 939 767 028 313 016 072 960 038 404 229 118 819 825 747 244 356 878 312 530 448 163 689 704 203 194 296 789 853 787 954 727 493 976 733 762 078 122 199 193 818 658 219 552 717 804 563 143 393 685 352 728 907 572 003 138 319 623 877 967 200 005 822 861 587 965 707 457 753 488 360 307 036 940 266 934 602 297 449 993 339 542 136 539 259 760 878 719 170 329 500 691 767 171 086 114 357 803 297 061 434 015 155 462 723 617 832 105 664 188 393 652 214 125 581 343 926 076 035 248 699 681 537 862 798 185 719 304 702 821 373 652 044 161 974 149 965 460 153 175 315 934
79.359   //C++结果，耗时79.359秒

forcal

前些日子，对Forcal进行了升级，完善了运算符重载功能。
重新改写FcHugeCalc，并以FcData（Forcal数据扩展动态库）为基础，这样FcHugeCalc中的代码更简单易懂。Forcal脚本代码也更为简洁。
FcHugeCalc源代码及演示程序下载地址没有变，新的说明如下：

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
        Forcal扩展库之FcHugeCalc：郭先强超大整数完全精度快速算法库
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

用法：

1、下载OpenFC，无需安装，仅需按readme设置好。

2、复制FcHugeCalc32W.dll和HugeCalc.dll两个文件到文件夹“OpenFC\dll”。

3、打开工作区文件“OpenFC.ini”，在#LOAD{... ...}中添加如下行：

        "dll\FcHugeCalc32W.dll"        //郭先强超大整数完全精度快速算法库

4、执行“设置->重载动态库扩展”。

5、可能需要注册后才能正常使用，参考“HugeCalc.chm”。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

当前可用的函数（都是整数函数，一般在oo函数中使用）：

1、HugeCalc::NewHC(HugeCalc::HI)、HugeCalc::NewHC(HugeCalc::HX)、HugeCalc::NewHC(HugeCalc::VUI32)：申请HugeInt对象、申请HugeIntX对象、申请VECTOR_UINT32对象

   说明：如果在oo函数中调用该函数，就返回临时对象，否则返回一般对象。一般对象须由函数delete销毁。

2、new(HugeCalc::HI)、new(HugeCalc::HX)、new(HugeCalc::VUI32)：申请HugeInt对象、申请HugeIntX对象、申请VECTOR_UINT32对象

   说明：new函数总是返回一般对象。一般对象须由函数delete销毁。

3、delete(p)：销毁对象p，一般p是由函数new返回的对象指针

4、HugeCalc::SetStr(p,"123")：给HugeCalc对象p赋值为123

   HugeCalc::SetNum(p,123)：给HugeCalc对象p赋值为123

   HugeCalc::HI(123)：申请HugeInt对象并赋值为123

   HugeCalc::HX(123)：申请HugeIntX对象并赋值为123

   p.=q：给HugeCalc对象p赋值为q，q也是HugeCalc对象。

5、HugeCalc::Show(p)：输出HugeCalc对象p的内容

   另外，用o(p)可查看对象信息。

6、HugeCalc::Pow(a,b)：计算a^b，a是HugeCalc对象，b为整数

   说明：如果在oo函数中调用该函数，就返回临时对象，否则返回一般对象。

7、HugeCalc::Fac(a,100)：计算a=100!

   说明：如果在oo函数中调用该函数，就返回临时对象，否则返回一般对象。

8、HugeCalc::NextPrime(a)：计算比a大的最小的素数

   说明：如果在oo函数中调用该函数，就返回临时对象，否则返回一般对象。

9、HugeCalc::Root(hugeRadicand, Exp, &pRemainder, &pIsReal)：高精度快速开方

   hugeRadicand：被开方数。HugeCalc对象。
   Exp：开方次数。整数。当 Exp≤1 时，返回值 = hugeRadicand, pRemainder = 0 。
   pRemainder：余数。返回HugeCalc临时对象。
   pIsReal：根是否为实数。当且仅当 Exp 为奇数且 hugeRadicand < 0 时，pIsReal = 0，否则 pIsReal != 0。当 pIsReal != 0 时，hugeRadicand = （返回值）^Exp + pRemainder，否则 hugeRadicand = - (返回值)^Exp + pRemainder。

   返回值：hugeRadicand 开 Exp 次方的根。如果在oo函数中调用该函数，就返回临时对象，否则返回一般对象。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

当前可用的运算符（只能在oo函数中使用）：

1、数学运算符，前置自增和前置自减运算符返回当前对象，其余返回临时对象

   +（加）、-（减）、*（乘）、/（除）、%（求模）、-（求负）、++（自增）、--（自减）

2、关系运算符，均返回逻辑值

   >（大于）、>=（大于等于）、<（小于）、<=（小于等于）、==（等于）、!=（不等于）

3、逻辑运算符，均返回逻辑值

   &（与）、|（或）、!（非）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

forcal

33＃的例子代码如下：

1. !using["HugeCalc","sys"];
   
2. mvar:
   
3. t0=clock();
   
4. i: (:a,c,aa)=oo{
   
5.      a=HI[10000000],
   
6.      b=HI[20000000],
   
7.      c=HI[0],
   
8.      a=NextPrime[a], aa=NextPrime[a],
   
9.      while{aa<=b,
   
10.        dd=a*aa, cc=Pow(aa,50),
    
11.        c.=c+Pow(a,100)*(a+aa)*(a*aa%(a+b))+(c+cc)/dd,
    
12.        a.=aa, aa.=NextPrime[aa]
    
13.      },
    
14.      printff["\r\n"], c.Show()
    
15.    };
    
16. [clock()-t0]/1000;

复制代码

结果和以前一样。耗时78.797秒。
耗时比以前略慢，原因：（1）新的FcHugeCalc以FcData为基础，多一次函数调用（但编写FcHugeCalc的复杂性降低了）；（2）使用.=进行对象赋值，比较简洁，但也多一些函数调用。

forcal

请问郭先生，CRadixConverter是否仅用于数制转换，是否还有其他用途？

另外，CVECTOR_UINT32对象该起一个什么名字比较好呢？例如CHugeInt对象我用HI表示（这样是否可以？）。

gxqcn

CRadixConverter 主要用于数制转换，也可将大数内部的值通过这种方式直接导出来，而不是以字串形式输出出来。
如果用户不需要该功能，则整个类不必提供出来。

关于给对象如何命名，可自由发挥。

forcal

37# gxqcn
谢谢郭先生！

还有一个问题，我在用Forcal的演示程序OpenFC测试FcHugeCalc时，发现OpenFC的一个监视窗口不能弹出（这个监视窗口当Forcal进行较长时间的运算时就会自动弹出），这是怎么回事？

是不是HugeCalc运行时线程的优先级比较高，而OpenFC的监视窗口线程具有一般的优先级，被屏蔽了？

forcal

接34＃的说明如下：

10、HugeCalc::NextPrime(a)：计算比a大的最小的素数

   说明：如果在oo函数中调用该函数，就返回临时对象，否则返回一般对象。

11、HugeCalc::SeedRandom(a)：设定随机发生器种子

   返回值：0。

12、HugeCalc::Random(a,Bits)：生成随机超大整数

   说明：a为HugeCalc对象，返回随机超大整数；Bits为位数。

13、HugeCalc::GeneratePrime(a,Bits)：生成随机超大素数

   说明：a为HugeCalc对象，返回随机超大素数；Bits为位数。

14、HugeCalc::IsPrime(a)：是否为素数

   返回值：逻辑值。

15、HugeCalc::TestPrimality(a,n)：超大整数绝对值的素性

   说明：a为HugeCalc对象；n为检测次数（若缺省n，默认值为5）。

   超大整数绝对值的素性：HugeCalc::COMPOSITE—确定为合数；HugeCalc::PROBABLY_PRIME—极可能为素数；HugeCalc::PRIME—肯定为素数

16、HugeCalc::Gcd(a,b,c,...,n)：高精度快速求最大公约数

   说明：a,b,c,...,n为HugeCalc对象，返回值也是HugeCalc对象。

17、HugeCalc::Lcm(a,b,c,...,n)：高精度快速求最小公倍数

   说明：a,b,c,...,n为HugeCalc对象，返回值也是HugeCalc对象。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

当前可用的运算符（只能在oo函数中使用）：

1、数学运算符，前置自增和前置自减运算符返回当前对象，其余返回临时对象

   +（加）、-（减）、*（乘）、/（除）、%（求模）、-（求负）、++（自增）、--（自减）

2、关系运算符，均返回逻辑值

   >（大于）、>=（大于等于）、<（小于）、<=（小于等于）、==（等于）、!=（不等于）

3、逻辑运算符，均返回逻辑值

   &（与）、|（或）、!（非）

说明：在写 a<b<c 的逻辑关系式时，应这样写：HI(a<b) & HI(b<c) 。函数HI用于将一个数（这里是一个逻辑值）转换为HugeInt对象。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

至此，对HugeCalc的封装暂时告一段落，虽没有完全封装HugeCalc，但主要的函数有了，可满足一般的需要。感兴趣的朋友可下载试用。

欢迎gxqcn 及各位朋友给出改进意见。

gxqcn

还有一个问题，我在用Forcal的演示程序OpenFC测试FcHugeCalc时，发现OpenFC的一个监视窗口不能弹出（这个监视窗口当Forcal进行较长时间的运算时就会自动弹出），这是怎么回事？

是不是HugeCalc运行时线程的优先级比较高，而OpenFC的监视窗口线程具有一般的优先级，被屏蔽了？
forcal 发表于 2010-10-25 21:12

不是的，是 HugeCalc 内含了反跟踪反破解技术。