数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › x86上128位二进制乘法最快速算法征解
1 ...789101112131415下一页
返回列表 发新帖
楼主: 无心人

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

[复制链接]
liangbch
发表于 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
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

G-Spider
发表于 2010-12-14 20:59:53 | 显示全部楼层
感觉n多时间消耗在函数调度上，而感受不到函数本身的内在价值。如果把运算次数作为一个参数，最速下降处理这个参数........，或许更好一点。可这样又或许对UInt128x128To256模块的设计不妥，因为我们通过不需要这个参数。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2010-12-15 08:06:34 | 显示全部楼层
131# liangbch 正好印证了我62#的猜测：
谢谢楼上的测试！ 看来不同机器对指令的处理周期相差很大， 也许在 Core2 上，56F 反超 58F 也是可能的。。。 gxqcn 发表于 2008-3-24 12:47
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mizne
发表于 2011-3-20 03:14:18 | 显示全部楼层
线程的创建和销毁代价也是非常大的
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

thewangj
发表于 2011-3-20 14:06:02 | 显示全部楼层
真是高手如云啊 佩服！学习中。。。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

smiler
发表于 2012-5-15 08:54:49 | 显示全部楼层
学习！ 准备将之修改到256×256的算法中去

评分

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

查看全部评分

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

guxd
发表于 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
                其余的函数不能通过编译，运行不了。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

l4m2
发表于 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
复制代码

点评

l4m2
直接轉寫成64位系統512*512位乘法，10 000 000次765.19ms，3 044 659 914周期。詳見https://pastebin.com/y95URZ0Y  发表于 2023-5-23 08:37
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1 ...789101112131415下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-11-15 10:04 , Processed in 0.026747 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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