API tools faq
paste
Advertisement
Zeda

karatsuba64

Zeda
Apr 16th, 2016
529
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Z80 Assembler 6.14 KB | None | 0 0
raw download clone embed print report
  1. Karatsuba64:
  2. ;Input: (word64_1),(word64_2)
  3. ;Output: (outp128)
  4. ;best   =1776+3*best(mul32)     =5292cc
  5. ;worst  =2243+3*worst(mul32)    =11165cc
  6. ;avg    =2009.5+3*avg(mul32)    =10011.8699cc
  7.  
  8.     ld hl,(word64_1) \ ld (word32_1),hl
  9.     ld hl,(word64_1+2) \ ld (word32_1+2),hl
  10.     ld hl,(word64_2) \ ld (word32_2),hl
  11.     ld hl,(word64_2+2) \ ld (word32_2+2),hl
  12.     call KaratsubaMul32
  13.     ld hl,(outp64) \ ld (outp128),hl
  14.     ld hl,(outp64+2) \ ld (outp128+2),hl
  15.     ld hl,(outp64+4) \ ld (outp128+4),hl
  16.     ld hl,(outp64+6) \ ld (outp128+6),hl
  17.  
  18.     ld hl,(word64_1+4) \ ld (word32_1),hl
  19.     ld hl,(word64_1+6) \ ld (word32_1+2),hl
  20.     ld hl,(word64_2+4) \ ld (word32_2),hl
  21.     ld hl,(word64_2+6) \ ld (word32_2+2),hl
  22.     call KaratsubaMul32
  23.     ld hl,(outp64) \ ld (outp128+8),hl
  24.     ld hl,(outp64+2) \ ld (outp128+10),hl
  25.     ld hl,(outp64+4) \ ld (outp128+12),hl
  26.     ld hl,(outp64+6) \ ld (outp128+14),hl
  27.  
  28. ;512+2*Karatsuba
  29.     xor a
  30.  
  31.     ld hl,(word64_1)
  32.     ld de,(word64_1+4)
  33.     add hl,de
  34.     ld (word32_1),hl
  35.     ld hl,(word64_1+2)
  36.     ld de,(word64_1+6)
  37.     adc hl,de
  38.     ld (word32_1+2),hl
  39.     rla
  40.  
  41.     ld hl,(word64_2)
  42.     ld de,(word64_2+4)
  43.     add hl,de
  44.     ld (word32_2),hl
  45.     ld hl,(word64_2+2)
  46.     ld de,(word64_2+6)
  47.     adc hl,de
  48.     ld (word32_2+2),hl
  49.     push af
  50.     call KaratsubaMul32
  51. ;790+3*Karatsuba
  52.     pop af
  53.     ld c,a
  54.     ld a,0
  55.     jr nc,Addmore_2
  56.     ld a,c
  57.     ld bc,(word64_1)
  58.     ld hl,(word64_1+4)
  59.     add hl,bc
  60.     ex de,hl
  61.     ld bc,(word64_1+2)
  62.     ld hl,(word64_1+6)
  63.     adc hl,bc
  64.     ex de,hl
  65.     ld bc,(outp64+4)
  66.     add hl,bc
  67.     ld (outp64+4),hl
  68.     ex de,hl
  69.     ld bc,(outp64+6)
  70.     adc hl,bc
  71.     ld (outp64+6),hl
  72.     ld c,a
  73.     ld a,0
  74.     adc a,c
  75. Addmore_2:
  76.     rr c
  77.     jr nc,label_2
  78.     ld bc,(word64_2)
  79.     ld hl,(word64_2+4)
  80.     add hl,bc
  81.     ex de,hl
  82.     ld bc,(word64_2+2)
  83.     ld hl,(word64_2+6)
  84.     adc hl,bc
  85.     ex de,hl
  86.     ld bc,(outp64+4)
  87.     add hl,bc
  88.     ld (outp64+4),hl
  89.     ex de,hl
  90.     ld bc,(outp64+6)
  91.     adc hl,bc
  92.     ld (outp64+6),hl
  93. label_2:
  94.     ld d,0 \ adc a,d
  95.  
  96. ;(outp64) - (outp128) - (outp128+8)
  97.     ld hl,(outp64)
  98.     ld bc,(outp128)
  99.     sbc hl,bc
  100.     ld (outp64),hl
  101.  
  102.     ld hl,(outp64+2)
  103.     ld bc,(outp128+2)
  104.     sbc hl,bc
  105.     ld (outp64+2),hl
  106.  
  107.     ld hl,(outp64+4)
  108.     ld bc,(outp128+4)
  109.     sbc hl,bc
  110.     ld (outp64+4),hl
  111.  
  112.     ld hl,(outp64+6)
  113.     ld bc,(outp128+6)
  114.     sbc hl,bc
  115.     ld (outp64+6),hl
  116.     sbc a,d
  117.  
  118.     ld hl,(outp64)
  119.     ld bc,(outp128+8)
  120.     sbc hl,bc
  121.     ld (outp64),hl
  122.  
  123.     ld hl,(outp64+2)
  124.     ld bc,(outp128+10)
  125.     sbc hl,bc
  126.     ld (outp64+2),hl
  127.  
  128.     ld hl,(outp64+4)
  129.     ld bc,(outp128+12)
  130.     sbc hl,bc
  131.     ld (outp64+4),hl
  132.  
  133.     ld hl,(outp64+6)
  134.     ld bc,(outp128+14)
  135.     sbc hl,bc
  136.     ld (outp64+6),hl
  137.     sbc a,d
  138.  
  139. ;(outp64) + (outp128+4)
  140.     ld hl,(outp64)
  141.     ld bc,(outp128+4)
  142.     add hl,bc
  143.     ld (outp128+4),hl
  144.  
  145.     ld hl,(outp64+2)
  146.     ld bc,(outp128+6)
  147.     adc hl,bc
  148.     ld (outp128+6),hl
  149.  
  150.     ld hl,(outp64+4)
  151.     ld bc,(outp128+8)
  152.     adc hl,bc
  153.     ld (outp128+8),hl
  154.  
  155.     ld hl,(outp64+6)
  156.     ld bc,(outp128+10)
  157.     adc hl,bc
  158.     ld (outp128+10),hl
  159.    
  160.     ld hl,(outp128+12)
  161.     ld e,a
  162.     adc hl,de
  163.     ld (outp128+12),hl
  164.     ret nc
  165.     ld hl,(outp128+14)
  166.     inc hl
  167.     ld (outp128+14),hl
  168.     ret
  169. .echo "  Karatsuba64:",$-Karatsuba64
  170. KaratsubaMul32:
  171. ;Input: (word32_1), (word32_2)
  172. ;Output: (outp64)
  173. ;worst: 925+3*worst(Mul)    2974cc
  174. ;best : 785+3*best(Mul)     1172cc
  175. ;avg  : 855+3*avg(Mul)      2667.4566cc
  176. ;Previous best optimized: 3666 t-states worst case, 2880 lower bound
  177. ;has a bug. For example, in pi*e, multiplying the upper 32 bits of each ends in A189, but should be a288
  178.  
  179.     ld bc,(word32_1)
  180.     ld de,(word32_2)
  181.     call BC_Times_DE
  182.     ld c,h
  183.     ld h,l
  184.     ld l,a
  185.     ld (outp),hl
  186.     ld (outp+2),bc
  187.  
  188.  
  189.     ld bc,(word32_1+2)
  190.     ld de,(word32_2+2)
  191.     call BC_Times_DE
  192.     ld c,h
  193.     ld h,l
  194.     ld l,a
  195.     ld (outp+4),hl
  196.     ld (outp+6),bc
  197.  
  198.     xor a
  199.     ld hl,(word32_1)
  200.     ld bc,(word32_1+2)
  201.     add hl,bc
  202.     rla
  203.     ex de,hl
  204.  
  205.     ld hl,(word32_2)
  206.     ld bc,(word32_2+2)
  207.     add hl,bc
  208.     ld b,h
  209.     ld c,l
  210.    
  211.     push af
  212.     call BC_Times_DE
  213.     ld e,h
  214.     ld d,b
  215.     ld h,l
  216.     ld l,a
  217. ;DEHL
  218.  
  219.     pop af
  220.     push hl
  221.     ld c,a
  222.     ld a,0
  223.     jr nc,Addmore_1
  224. ;(ax+b)(cx+d) = acx^2+axd+bcx+bd
  225. ;c flag is c
  226. ;
  227. ;x=2^16
  228. ;a,c are 0 or 1
  229. ;  If a = 1, add c to A (A is the overflow thing), add (word32_2)+(word32_2+2) to DE
  230. ;  If c = 1, add b to DE
  231.     ld a,c
  232.     ld bc,(word32_1)
  233.     ld hl,(word32_1+2)
  234.     add hl,bc
  235.     add hl,de
  236.     ex de,hl
  237.     ld c,a
  238.     ld a,0
  239.     adc a,c
  240. Addmore_1:
  241.     rr c
  242.     jr nc,label_1
  243. ;if bit 7 is set, A =2, else A=0
  244.     ld bc,(word32_2)
  245.     ld hl,(word32_2+2)
  246.     add hl,bc
  247.     add hl,de
  248.     ex de,hl
  249.     adc a,0
  250. label_1:
  251.     pop hl
  252.  
  253.  
  254. ;ADEHL - (outp) - (outp+4)
  255.     ld bc,(outp)
  256. ;   or a
  257.     sbc hl,bc
  258.     ex de,hl
  259. ;HLDE
  260.     ld bc,(outp+2)
  261.     sbc hl,bc \ sbc a,0
  262.     ex de,hl
  263. ;DEHL
  264.     ld bc,(outp+4)
  265.     sbc hl,bc
  266.     ex de,hl
  267. ;HLDE
  268.     ld bc,(outp+6)
  269.     sbc hl,bc \ sbc a,0
  270.     ex de,hl
  271. ;DEHL + (outp+2)
  272.     ld bc,(outp+2)
  273.     add hl,bc
  274.     ld (outp+2),hl
  275.     ex de,hl
  276. ;HLDE
  277.  
  278.     ld bc,(outp+4)
  279.     ld de,(outp+6)
  280.     adc hl,bc
  281.     ld (outp+4),hl
  282.     ld h,0 \ ld l,a
  283.     adc hl,de
  284.     ld (outp+6),hl
  285.     ret
  286. .echo "  Karatsuba32:",$-KaratsubaMul32
  287. BCM:
  288. BC_Times_DE:
  289. ;BC*DE->BHLA
  290. ;out: E=0, A,D are destroyed
  291. ;Assuming B=0, C=0      129cc
  292. ;Assuming B!=0,C=0      329cc~410cc, avg 373cc-3.5
  293. ;         B=0, C!=0
  294. ;Assuming B!=0,C!=0     529cc~683cc, avg 609.5cc-3.5cc
  295. ;Overall average: 79187439/131072=604.15221405029296875cc
  296.  
  297.  
  298.     ld a,b
  299.     ld hl,0
  300.     ld b,h
  301.     or a
  302.     jr z,+_
  303.             add a,a \ jr nc,$+5 \ ld h,d \ ld l,e
  304.     add hl,hl \ rla \ jr nc,$+4 \ add hl,de \ adc a,b
  305.     add hl,hl \ rla \ jr nc,$+4 \ add hl,de \ adc a,b
  306.     add hl,hl \ rla \ jr nc,$+4 \ add hl,de \ adc a,b
  307.     add hl,hl \ rla \ jr nc,$+4 \ add hl,de \ adc a,b
  308.     add hl,hl \ rla \ jr nc,$+4 \ add hl,de \ adc a,b
  309.     add hl,hl \ rla \ jr nc,$+4 \ add hl,de \ adc a,b
  310.     add hl,hl \ rla \ jr nc,$+4 \ add hl,de \ adc a,b
  311. _:
  312.     push hl
  313.     ld h,b
  314.     ld l,b
  315.     ld b,a
  316.     ld a,c
  317.     ld c,b
  318.     or a
  319.     jr z,+_
  320.             add a,a \ jr nc,$+5 \ ld h,d \ ld l,e
  321.     add hl,hl \ rla \ jr nc,$+4 \ add hl,de \ adc a,c
  322.     add hl,hl \ rla \ jr nc,$+4 \ add hl,de \ adc a,c
  323.     add hl,hl \ rla \ jr nc,$+4 \ add hl,de \ adc a,c
  324.     add hl,hl \ rla \ jr nc,$+4 \ add hl,de \ adc a,c
  325.     add hl,hl \ rla \ jr nc,$+4 \ add hl,de \ adc a,c
  326.     add hl,hl \ rla \ jr nc,$+4 \ add hl,de \ adc a,c
  327.     add hl,hl \ rla \ jr nc,$+4 \ add hl,de \ adc a,c
  328. _:
  329.     pop de
  330.     ld c,a
  331.     ld a,l
  332.     ld l,h
  333.     ld h,c
  334.     add hl,de
  335.     ret nc
  336.     inc b
  337.     ret
  338. .echo "  Base Mult  :",$-BCM
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!