找回密码
 欢迎注册
楼主: 无心人

[擂台] x86上128位二进制乘法最快速算法征解

[复制链接]
发表于 2010-12-14 18:46:02 | 显示全部楼层
贴上在E8500的运行结果,函数包含至105楼。

Test function: UInt128x128To256_ANSI_C32(..) 10000000 times...
Elapsed time: 896.603 ms
  21BC4991 10D8039C A196539D 146A3CBE * E3580EAB 9F5C4DAD D4D6030B 4E7C3B55
= 1DF58FE3 D59883DF 459F83F8 724F3842   3D686D6C 1EA80B08 E6980EFD 934DF516

Test function: UInt128x128To256_SSE2_40F(..) 10000000 times...
Elapsed time: 335.639 ms
  21BC4991 10D8039C A196539D 146A3CBE * E3580EAB 9F5C4DAD D4D6030B 4E7C3B55
= 1DF58FE3 D59883DF 459F83F8 724F3842   3D686D6C 1EA80B08 E6980EFD 934DF516

Test function: UInt128x128To256_SSE2_42F(..) 10000000 times...
Elapsed time: 302.855 ms
  21BC4991 10D8039C A196539D 146A3CBE * E3580EAB 9F5C4DAD D4D6030B 4E7C3B55
= 1DF58FE3 D59883DF 459F83F8 724F3842   3D686D6C 1EA80B08 E6980EFD 934DF516

Test function: UInt128x128To256_SSE2_54F(..) 10000000 times...
Elapsed time: 310.400 ms
  21BC4991 10D8039C A196539D 146A3CBE * E3580EAB 9F5C4DAD D4D6030B 4E7C3B55
= 1DF58FE3 D59883DF 459F83F8 724F3842   3D686D6C 1EA80B08 E6980EFD 934DF516

Test function: UInt128x128To256_SSE2_56F(..) 10000000 times...
Elapsed time: 264.212 ms
  21BC4991 10D8039C A196539D 146A3CBE * E3580EAB 9F5C4DAD D4D6030B 4E7C3B55
= 1DF58FE3 D59883DF 459F83F8 724F3842   3D686D6C 1EA80B08 E6980EFD 934DF516

Test function: UInt128x128To256_SSE2_58F(..) 10000000 times...
Elapsed time: 271.680 ms
  21BC4991 10D8039C A196539D 146A3CBE * E3580EAB 9F5C4DAD D4D6030B 4E7C3B55
= 1DF58FE3 D59883DF 459F83F8 724F3842   3D686D6C 1EA80B08 E6980EFD 934DF516

Test function: UInt128x128To256_SSE2_69F(..) 10000000 times...
Elapsed time: 282.345 ms
  21BC4991 10D8039C A196539D 146A3CBE * E3580EAB 9F5C4DAD D4D6030B 4E7C3B55
= 1DF58FE3 D59883DF 459F83F8 724F3842   3D686D6C 1EA80B08 E6980EFD 934DF516

Test function: UInt128x128To256_SSE2_93F(..) 10000000 times...
Elapsed time: 374.652 ms
  21BC4991 10D8039C A196539D 146A3CBE * E3580EAB 9F5C4DAD D4D6030B 4E7C3B55
= 1DF58FE3 D59883DF 459F83F8 724F3842   3D686D6C 1EA80B08 E6980EFD 934DF516

Test function: UInt128x128To256_SSE2_96F(..) 10000000 times...
Elapsed time: 265.366 ms
  21BC4991 10D8039C A196539D 146A3CBE * E3580EAB 9F5C4DAD D4D6030B 4E7C3B55
= 1DF58FE3 D59883DF 459F83F8 724F3842   3D686D6C 1EA80B08 E6980EFD 934DF516

Test function: UInt128x128To256_SSE2_102F(..) 10000000 times...
Elapsed time: 400.549 ms
  21BC4991 10D8039C A196539D 146A3CBE * E3580EAB 9F5C4DAD D4D6030B 4E7C3B55
= 1DF58FE3 D59883DF 459F83F8 724F3842   3D686D6C 1EA80B08 E6980EFD 934DF516

Test function: UInt128x128To256_SSE2_105F(..) 10000000 times...
Elapsed time: 292.557 ms
  21BC4991 10D8039C A196539D 146A3CBE * E3580EAB 9F5C4DAD D4D6030B 4E7C3B55
= 1DF58FE3 D59883DF 459F83F8 724F3842   3D686D6C 1EA80B08 E6980EFD 934DF516
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-12-14 20:59:53 | 显示全部楼层
感觉n多时间消耗在函数调度上,而感受不到函数本身的内在价值。如果把运算次数作为一个参数,最速下降处理这个参数........,或许更好一点。可这样又或许对UInt128x128To256模块的设计不妥,因为我们通过不需要这个参数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-12-15 08:06:34 | 显示全部楼层
131# liangbch

正好印证了我62#的猜测:
谢谢楼上的测试!

看来不同机器对指令的处理周期相差很大,
也许在 Core2 上,56F 反超 58F 也是可能的。。。
gxqcn 发表于 2008-3-24 12:47
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-3-20 03:14:18 | 显示全部楼层
线程的创建和销毁代价也是非常大的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-3-20 14:06:02 | 显示全部楼层
真是高手如云啊
佩服!学习中。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-5-15 08:54:49 | 显示全部楼层
学习! 准备将之修改到256×256的算法中去

评分

参与人数 1金币 +20 收起 理由
gxqcn + 20 首贴奖励,欢迎常来。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-7-6 08:49:17 | 显示全部楼层
楼主真厉害
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-11-4 11:37:21 | 显示全部楼层
有最新CPU的同学更新下测试结果,另外,是不是需要弄个SSE4.2跟AVX2的版本来?

还有,64位也测试下?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-11-27 13:30:32 | 显示全部楼层
本帖最后由 只是呼吸 于 2014-11-27 13:33 编辑

我用我的这台计算机试了一下。
   机器数据: 操作系统  win7
                        cpu   Intel(R) Core(TM) i3-3240 cpu @ 3.40GHz  3.40GHz
                        内存   4.0GB(3.47GB可用)
              系统类型    32位操作系统

   编译系统     vc++6.0

                对函数"UInt128x128To256_ANSI_C32"的测试结果是 10000000次  1023.014ms
                对函数"UInt128x128To256_ALU_102F"的测试结果是 10000000次  280.132ms
                其余的函数不能通过编译,运行不了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-5-20 02:04:57 | 显示全部楼层
用15年後的電腦,限制使用16位(8086)指令,10 000 000次耗時2.5秒。
  1.         org 100h
  2. L0:
  3.         mov BX, mul1
  4.         mov SI, mul2
  5.         mov DI, mulF
  6.         call mult
  7.         dec dword [counter]
  8.         jnz L0
  9.         ret
  10.        
  11.         db 11Ch-$ dup ?
  12. counter:
  13.         dd 10000000
  14.         db 120h-$ dup ?
  15. mul1:
  16.         dq -1, -1
  17. mul2:
  18.         dq -1, -1
  19. mulF:
  20.         dq 4 dup ?
  21.        
  22. mult:
  23.         ; Input SI
  24.         ; Input BX
  25.         ; Output DI
  26.         ; Destroy ALL
  27.         ; Buffer BX CX BP
  28.        
  29.         rept 8 i:-7 {
  30.                 mov AX, [BX-2*i]
  31.                 mov [DI+16-2*i], AX
  32.         }
  33.         mul word [SI]
  34.         display 48+0, 48+(0), 32
  35.         mov [DI], AX
  36.         mov BX, DX
  37.         xor CX, CX
  38.         Z1 equ BX
  39.         Z2 equ CX
  40.         Z3 equ BP
  41.         rept 7 i: 1 {
  42.                 xor Z3, Z3
  43.                 rept i+1 j: 0 \{
  44.                         mov AX, [DI+16+2*j]
  45.                         mul word [SI+2*i-2*j]
  46.                         display 48+j, 48+(i-j), 32
  47.                         add Z1, AX
  48.                         adc Z2, DX
  49.                         adc Z3, 0
  50.                 \}
  51.                 mov [DI+2*i], Z1
  52.                 Z4 equ Z1
  53.                 Z1 equ Z2
  54.                 Z2 equ Z3
  55.                 Z3 equ Z4
  56.         }
  57.         rept 7 i: 8 {
  58.                 if i < 14
  59.                         xor Z3, Z3
  60.                 end if
  61.                 rept 15-i j: i-7 \{
  62.                         mov AX, [DI+16+2*j]
  63.                         mul word [SI+2*i-2*j]
  64.                         display 48+j, 48+(i-j), 32
  65.                         add Z1, AX
  66.                         adc Z2, DX
  67.                         if i < 14
  68.                                 adc Z3, 0
  69.                         end if
  70.                 \}
  71.                 mov [DI+2*i], Z1
  72.                 Z4 equ Z1
  73.                 Z1 equ Z2
  74.                 Z2 equ Z3
  75.                 Z3 equ Z4
  76.         }
  77.         mov [DI+30], Z1
  78.         ret
复制代码


作為對比,5億次16位乘法耗時1秒:
  1. org 100h
  2. mov ecx, 500000000
  3. L:
  4. mov ax, [bp]
  5. mul word [bp+2]
  6. dec ecx
  7. jnz L
  8. ret
复制代码

点评

直接轉寫成64位系統512*512位乘法,10 000 000次765.19ms,3 044 659 914周期。詳見https://pastebin.com/y95URZ0Y  发表于 2023-5-23 08:37
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 16:27 , Processed in 0.049673 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表