ABAP 大数相乘【递归思想应用】

计算机中数据定义的长度是有限的，比如31位，或者63位，外加一位符号位。
  1 *&---------------------------------------------------------------------*
  2 *& Report  ZCHENH048
  3 *&
  4 *&---------------------------------------------------------------------*
  5 *&
  6 *&
  7 *&---------------------------------------------------------------------*
  8 
  9 REPORT zchenh048.
 10 *算法参考思想：https://blog.csdn.net/u010983881/article/details/77503519
 11 DATA:num1 TYPE string,
 12      num2 TYPE string,
 13      result TYPE string.
 14 num1 = 123456789.
 15 num2 = 123456789.
 16 CONDENSE:num1,num2.
 17 PERFORM frm_big_mult USING num1 num2 CHANGING result.
 18 WRITE:num1,'x',num2,'=',result.
 19 *&---------------------------------------------------------------------*
 20 *&      Form  FRM_BIG_MULT
 21 *&---------------------------------------------------------------------*
 22 *       text
 23 *----------------------------------------------------------------------*
 24 *  -->  p1        text
 25 *  <--  p2        text
 26 *----------------------------------------------------------------------*
 27 FORM frm_big_mult USING value(n1)
 28                          value(n2)
 29                CHANGING res.
 30   DATA:lv_len1 TYPE i,
 31        lv_len2 TYPE i,
 32        halfn TYPE i,
 33        mid TYPE i.
 34 
 35   DATA:a TYPE string,
 36         b TYPE string,
 37         c TYPE string,
 38         d TYPE string,
 39         x TYPE string,
 40         y TYPE string.
 41   DATA:z0 TYPE string,
 42         z1 TYPE string,
 43         z2 TYPE string.
 44 
 45 *递归终止条件
 46   IF n1 < 10 OR n2 < 10.
 47     res = n1 * n2.
 48   ELSE.
 49 *     计算拆分长度
 50     CLEAR:lv_len1,lv_len2,halfn.
 51     CONDENSE: n1,n2.
 52     lv_len1 = strlen( n1 ).
 53     lv_len2 = strlen( n2 ).
 54 
 55     IF lv_len1 > lv_len2.
 56       halfn = floor( lv_len1 / 2 ). " 向下取整
 57     ELSE.
 58       halfn = floor( lv_len2 / 2 ).
 59     ENDIF.
 60 *    WRITE:/,'HALFN--->',halfn,'lv_len1--->',lv_len1,'lv_len2--->',lv_len2.
 61     mid = lv_len1 - halfn.
 62     a = n1+0(mid).
 63     b = n1+mid(halfn).
 64 
 65     mid = lv_len2 - halfn.
 66     c = n2+0(mid).
 67     d = n2+mid(halfn).
 68 
 69     x = a + b.
 70     y = c + d.
 71 
 72 *    WRITE:/,'a-->',a,'b-->',b,'c-->',c,'d-->',d,'x-->',x,'y-->',y.
 73 * 计算z2, z0, z1, 此处的乘法使用递归
 74     PERFORM frm_big_mult USING a c CHANGING z2.
 75     PERFORM frm_big_mult USING b d CHANGING z0.
 76     PERFORM frm_big_mult USING x y CHANGING z1.
 77     z1 = z1 - z0 - z2.
 78 *    WRITE:/,'z0-->',z0,'z1-->',z1,'z2-->',z2.
 79     PERFORM frm_math_n USING 10  2 halfn z2 CHANGING a. " 求N次方
 80     PERFORM frm_math_n USING 10  1 halfn z1 CHANGING b. " 求N次方
 81     res = a + b + z0 .
 82   ENDIF.
 83 ENDFORM.   " FRM_BIG_MULT
 84 *&---------------------------------------------------------------------*
 85 *&      Form  FRM_MATH_N
 86 *&---------------------------------------------------------------------*
 87 *       text
 88 *----------------------------------------------------------------------*
 89 *  -->  p1        text
 90 *  <--  p2        text
 91 *----------------------------------------------------------------------*
 92 FORM frm_math_n USING a1 b1 c1 d1 CHANGING e1 TYPE string.
 93   DATA: res TYPE n LENGTH 30 .
 94   res = a1 ** ( b1 * c1 ).
 95   e1 = res * d1.
 96 ENDFORM.                    " FRM_MATH_N
 97 
 98 
 99 * JAVA版
100 *public class HelloWorld {
101 *    public static void main(String []args) {
102 *   long num1 = 1234567899;
103 *   long num2 = 1234567899;
104 *       System.out.println("大数相乘："+num1+" X "+num2+" = "+ karatsuba(num1,num2));
105 *    }
106 *    public static long karatsuba(long num1, long num2){
107 *    //递归终止条件
108 *    if(num1 < 10 || num2< 10) return num1 * num2;
109 *
110 *    // 计算拆分长度
111 *    int size1 = String.valueOf(num1).length();
112 *    int size2 = String.valueOf(num2).length();
113 *    int halfN = Math.max(size1, size2) / 2;
114 *
115 *    /* 拆分为a, b, c, d */
116 *    long a = Long.valueOf(String.valueOf(num1).substring(0, size1 - halfN));
117 *    long b = Long.valueOf(String.valueOf(num1).substring(size1 - halfN));
118 *    long c = Long.valueOf(String.valueOf(num2).substring(0, size2 - halfN));
119 *    long d = Long.valueOf(String.valueOf(num2).substring(size2 - halfN));
120 *
121 *    // 计算z2, z0, z1, 此处的乘法使用递归
122 *    long z2 = karatsuba(a, c);
123 *    long z0 = karatsuba(b, d);
124 *    long z1 = karatsuba((a + b), (c + d)) - z0 - z2;
125 *
126 *    return (long)(z2 * Math.pow(10, (2*halfN)) + z1 * Math.pow(10, halfN) + z0);
127 *}
128 *}
View Code
运行结果：123456789 x 123456789 = 15241578750190521.0
欢迎访问我的博客！ http://www.cnblogs.com/1187163927ch/