fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main() {
  5.  
  6. private static String pad ( final String x, final int n)
  7.     {
  8.     String res = new String(x);
  9.     for (int i=1; i<=n; i++)
  10.       {
  11.       res = "0"+res;
  12.       };
  13.     return res;
  14.     }           /** of pad */
  15.   /**
  16.    * Remove leading '0's from string x
  17.   */
  18.   private static String trim_down ( final String x )
  19.     {
  20.     String res = new String(x);
  21.     while (res.startsWith("0"))
  22.       {
  23.       res = res.substring(1);
  24.       };
  25.     return res;
  26.     } /** of trim_down */
  27.   /**
  28.    * Shift (i.e. Multiply by 10^n)
  29.   */
  30.   public static String shift_n (final String x, final int n)
  31.     {
  32.     String res = new String(x);
  33.     for (int i=1; i<=n; i++)
  34.       {
  35.       res=res+"0";
  36.       };
  37.     return res;
  38.     }         /** of shift_n */
  39.  
  40.   /**
  41.    * Subtraction x-y where x >= y assumed
  42.   */
  43.   public static String monus(final String x, final String y)
  44.     {
  45.     char[] tx = new String(x).toCharArray();   /** Process x as char array. */
  46.     char[] ty = new String(y).toCharArray();   /** Process y as char array. */
  47.     String res = new String("");               /** Eventual result. */
  48.     char borrow = '0';                         /** Borrow digit. */
  49.     int i;                                     /** Loop counter. */
  50.     /**
  51.      * Pad tx/ty to same length if necessary.
  52.     */
  53.     if ( !(tx.length==ty.length) )
  54.       {
  55.       int diff = tx.length-ty.length;
  56.       if (diff<0)
  57.         {
  58.         tx = pad(x,-diff).toCharArray();
  59.         }
  60.       else
  61.         {
  62.         ty = pad(y,diff).toCharArray();
  63.         };
  64.       };
  65.      /** 
  66.       * Main subtraction calculation (N.B. tx[0] is most sig. digit, hence
  67.       *                               loop iterate for tx.length-1 to 0)
  68.      */
  69.      for (i=tx.length-1; i>=0; i=i-1)
  70.        {
  71.        int bx = (int)tx[i] - (int)borrow;    /** Convert tx[i] remembering borrow. */
  72.        int by = (int)ty[i]-(int)'0';         /** Convert ty[i]. */
  73.        int tv = bx-by;                       /** Result digit */
  74.        /**
  75.         * Update borrow and correct tv if needed.
  76.        */
  77.        if (tv<0)
  78.          {
  79.          borrow='1'; tv=tv+10;
  80.          }
  81.        else
  82.          {
  83.          borrow='0';
  84.          };
  85.        res=(char) ( tv+(int)'0')+res;   /** Pack digit into result string. */
  86.        };
  87.        return res;
  88.      }        /** of monus */
  89.   /**
  90.    * Addition. 
  91.    * Much the same as monus method (but with carry instead of borrow).
  92.   */
  93.   public static String add(final String x, final String y)
  94.     {
  95.     char[] tx = new String(x).toCharArray();
  96.     char[] ty = new String(y).toCharArray();
  97.     String res = new String("");
  98.     char carry = '0';
  99.     int i;
  100.     if ( !(tx.length==ty.length) )
  101.       {
  102.       int diff = tx.length-ty.length;
  103.       if (diff<0)
  104.         {
  105.         tx = pad(x,-diff).toCharArray();
  106.         }
  107.       else
  108.         {
  109.         ty = pad(y,diff).toCharArray();
  110.         };
  111.       };
  112.     for (i=tx.length-1; i>=0; i=i-1)
  113.       {
  114.       int tv = (int)tx[i]-(int)'0' +(int)ty[i]-(int)'0' +(int)carry - (int)'0';
  115.       if (tv>9)
  116.         {
  117.         carry='1'; tv=tv-10;
  118.         }
  119.       else
  120.         {
  121.         carry='0';
  122.         };
  123.       res=(char) ( tv+(int)'0')+res;
  124.       };
  125.     if (carry=='1') 
  126.       {
  127.       res = "1"+res;
  128.       };
  129.     return res;
  130.     }
  131.    /**
  132.     * Multiplication using Karatsuba Method
  133.    */
  134.    public static String multiply ( final String x, final String y)
  135.      {
  136.      char[] tx = new String(x).toCharArray();
  137.      char[] ty = new String(y).toCharArray();
  138.      int n;                               /** Number of digits in (even length) tx. */
  139.      String res = new String();
  140.      /**
  141.      *  Equalise Lengths before computation
  142.      */
  143.      if ( !(tx.length==ty.length) )
  144.        {
  145.        int diff = tx.length-ty.length;
  146.        if (diff<0)
  147.          {
  148.          tx = pad(x,diff).toCharArray();
  149.          }
  150.        else
  151.          {
  152.          ty = pad(y,diff).toCharArray();
  153.          }; 
  154.        };
  155.      /**
  156.       * Recursive Base (4 or fewer digits)
  157.      */
  158.      int mx = Math.max(tx.length, ty.length);
  159.      if (mx <= 4)
  160.        {
  161.        res = String.valueOf ( new BigInteger(new String(tx)).multiply(new BigInteger(new String(ty))));
  162.        return res;
  163.        }
  164.      else      /** Number of digits > 4 so recurse. */
  165.        {
  166.        if (tx.length%2==1)
  167.          {
  168.          tx= pad(String.valueOf(tx),1).toCharArray();  /** Add leading 0 if odd length; */
  169.          ty= pad(String.valueOf(ty),1).toCharArray();
  170.          };
  171.        n = tx.length;
  172.        /**
  173.         * DIVIDE STAGE: 
  174.         *
  175.         * Form appropriate substrings: tx, tx are n digit
  176.         * equivalents of x,y where n is even.
  177.         *
  178.         *  a = (n/2) Most significant digits x
  179.         *  b=  (n/2) Least significant digits x
  180.         *  c = (n/2) Most significant digits y
  181.         *  d=  (n/2) Least significant digits y
  182.        */
  183.        String a = new String( (String.valueOf(tx)).substring(0,n/2) );
  184.        String b = new String( (String.valueOf(tx)).substring(n/2,n) );
  185.        String c = new String( (String.valueOf(ty)).substring(0,n/2) );
  186.        String d = new String( (String.valueOf(ty)).substring(n/2,n) );
  187.        /**
  188.         * Now form the representations for a+b, c+d (arithmetic addition)
  189.        */
  190.        String a_plus_b = new String ( add(a,b) );
  191.        String c_plus_d = new String ( add(c,d) );
  192.        /**
  193.         * CONQUER STAGE
  194.         *
  195.         * Recursive Invocations:
  196.         *      u=a*c; v=b*d; w=(a+b)*(c+d)
  197.        */
  198.        String u = new String (multiply(a,c));
  199.        String v = new String (multiply(b,d));
  200.        String w = new String (multiply(a_plus_b,c_plus_d));
  201.        /**
  202.         * COMBINE STAGE
  203.         *
  204.         * Compute: u*10^n + (w-(u+v))*10^(n/2) + v
  205.         *         = (a*10^(n/2)+b)*(c*10^(n/2)+d)
  206.         *         = x*y
  207.         *
  208.         * s*10^k performed by shift_n(s,k);
  209.         * Result is stripped of superfluous leading '0's
  210.        */
  211.        String u_plus_v = new String ( add(u,v) );
  212.        String w_monus_uv = new String ( monus(w,u_plus_v) );
  213.        String res1 = new String ( shift_n(u,n) );
  214.        String res2 = new String ( add(res1,shift_n(w_monus_uv,n/2)) );
  215.        String res3 = new String ( add(res2,v) );
  216.        return trim_down(res3);
  217.        }
  218.      }
  219. 	return 0;
  220. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:6:1: error: expected primary-expression before ‘private’
 private static String pad ( final String x, final int n)
 ^
prog.cpp:6:1: error: expected ‘;’ before ‘private’
prog.cpp:220:1: error: expected ‘}’ at end of input
 }
 ^
stdout
copy 
Standard output is empty
https://ideone.com/gdZEiP
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!