/* * Copyright (c) 2014 Zhikai Wang/www.heteroclinic.net. All rights reserved. * * Please read the following: * License or agreement of usage terms * 1. Science and technology promotion license applied, all third party licenses and rights or legal documents * are automatically cascaded. * 2. Non-commercial usage of this file is not limited (Zhikai Wang/www.heteroclinic.net's rights). * 3. Commercial usage is allowed, given file(s) of origin is not modified. * Inheritance/overriding/re-factoring is suggested at higher level and allowed. * 4. This is a good-will software. Users' liability always. * 5. The liability of Zhikai Wang/www.heteroclinic.net to the maximum is to modify/remove matters in dispute. * GIVEN you acknowledge agree 1 to 5, or just kindly acknowledge the contribution of the author accordingly, * YOU CAN DO ANYTHING at good-will with this software. The inverse of good-will behavior includes * illegal activities that are subject to jurisdiction applicable. */ package net.heteroclinic.experiment.overflow; public class SumExperiment { public static final int BitsPerComputeUnit = 31; public static final int Exp_MAX_VALUE = powIterate (2, BitsPerComputeUnit) -1; public static int powIterate( int x, int y) { int result = x; for (int i=2; i<=y; i++) { result *=x; } return result; } // public static int [] sumWithIntCarry (int a, int b) { // return new int []{ Exp_MAX_VALUE - a < b ? 1:0, }; // } /** * * @param a * @param b * @param BitsPerComputeUnit * @return the least significant unit is at the 0 index of the array, so on so forth. */ public static int [] sumWithIntCarry (int a, int b, int BitsPerComputeUnit) { int Exp_MAX_VALUE = powIterate (2, BitsPerComputeUnit) -1; boolean overflowCondition = Exp_MAX_VALUE - a < b; return new int []{ overflowCondition?b- (Exp_MAX_VALUE-a+1): a+b ,overflowCondition ? 1:0 }; } public static String toIntArraySting (int [] arr) { return toIntArraySting (arr, true); } public static String toIntArraySting (int [] arr, boolean startWithLeastSignificantUnit) { String result = ""; if (null == arr || arr.length<= 0 ) return result; result += "["; if (startWithLeastSignificantUnit) { for (int i = 0 ; i < arr.length; i++) { result += arr[i] + ","; } } else { for (int i = arr.length-1 ; i>=0; i--) { result += arr[i] + ","; } } result += "]"; result = result.replace(",]", "]"); return result; } public static void main(String[] args) { System.out.println("Experiment 1 some reconnaissance"); System.out.println(Integer.MAX_VALUE);//2147483647 System.out.println((int)Math.pow(2, 31) - 1);//2147483646??//i7 CPU, tricky? System.out.println( powIterate( 2, 31) - 1);//2147483647!! //int java.lang.Integer.MAX_VALUE = 2147483647 [0x7fffffff] //A constant holding the maximum value an int can have, $$2^31-1$$.//Latex Math System.out.println(new int[] {1,2});//no way print a pointer System.out.println(",]".replace(",]","]"));//Good. System.out.println(toIntArraySting(new int[] {1,2}));//[a,b] should be a* (MAX+1) + b by value. System.out.println(toIntArraySting(new int[] {1,2},false));// [a,b] should be b* (MAX+1) + a by value. System.out.println("\n\n"); System.out.println("Experiment 2 test if you can handle sum overflow"); System.out.println(toIntArraySting( sumWithIntCarry (13, 14,4) )); // should return [11,1] = 11 + 16 is 27 //OK System.out.println(toIntArraySting( sumWithIntCarry (13, 3,4) )); //[0,1]?! System.out.println(toIntArraySting( sumWithIntCarry (Integer.MAX_VALUE, 1,31) )); //[0,1]?! System.out.println(toIntArraySting( sumWithIntCarry (Integer.MAX_VALUE, 12,31) )); //?[11,1]! System.out.println(toIntArraySting( sumWithIntCarry (Integer.MAX_VALUE, Integer.MAX_VALUE/2,31) )); //?[1073741822,1]! System.out.println(toIntArraySting( sumWithIntCarry (Integer.MAX_VALUE/2, 5,31) )); //? [1073741828,0]! System.out.println("So far so good."); System.out.println("\n\n"); } }

Given M >= a >= b > 0, for b =0, no overflow will happen. Let k be a*k just overflows above m, but a*(k-1) not, namely a*k >M but a*(k-1)<=M. c = b/k (integer division) r = b%k a * b = a * c * k + a * r For a * r < a * k , it is safe. For a * c * k: We know a * k is the ceiling overflow about m; so a * k = a * (k-1) + a < 2M, why? a*(k-1) had no overflow, $$a$$ not an overflow value, each part is less than M. The above line states a * k will bring the carry exactly as 1. Then a * k % (M + 1) can be computed by a*k-M-1. The remainder a*k %(M+1) = a*(k-1) -M -1 + a; We know M < a*k < 2M, a - M -1 <0 but | a -M -1| < a*(k-1) <M. Use a * (k-1) -M -1 + a is overflow safe, you can not alter the sequence and this is signed value computation. Things look went crazy and reluctant to be reined under control as we wished as simple as 1+1=2. But so far what we get: we know a*c*k brings up c carries since a*k brings up exactly one carry. But the remainder ( a * (k-1) -M -1 + a )* c can also brings up carry even greater than one, and leave some remainders? Given such a question, we know we can remove c carry from a*k*c, in a recursive call ( a * (k-1) -M -1 + a )* c will keep decreasing and finally hit the condition of no overflow as previous steps handled. Is this something meaningful? Review the logical gates circuit design, a multiplication circuit uses a truth table. Each one more bit added, the size of the truth table will double. The multiplication circuit within my understanding is almost a hard-code way of bits operations. The ideal mathematical operations are far beyond the capacity of transistors' circuit. Some time in floating point computation a*b may not equal b*a. We stop here the discussion and use, recursion, safe way of adding integers (resulting array of integers) to see if what we discuss can do what they are supposed to do. In brief, we can compute carry value, then keep the remainder smaller then enter the recursion until no overflow happens.

/* * Copyright (c) 2014 Zhikai Wang/www.heteroclinic.net. All rights reserved. * * Please read the following: * License or agreement of usage terms * 1. Science and technology promotion license applied, all third party licenses and rights or legal documents * are automatically cascaded. * 2. Non-commercial usage of this file is not limited (Zhikai Wang/www.heteroclinic.net's rights). * 3. Commercial usage is allowed, given file(s) of origin is not modified. * Inheritance/overriding/re-factoring is suggested at higher level and allowed. * 4. This is a good-will software. Users' liability always. * 5. The liability of Zhikai Wang/www.heteroclinic.net to the maximum is to modify/remove matters in dispute. * GIVEN you acknowledge agree 1 to 5, or just kindly acknowledge the contribution of the author accordingly, * YOU CAN DO ANYTHING at good-will with this software. The inverse of good-will behavior includes * illegal activities that are subject to jurisdiction applicable. */ package net.heteroclinic.experiment.overflow; public class MultiplicationExperiment { public static final int BitsPerComputeUnit = 31; public static final int Exp_MAX_VALUE =SumExperiment. powIterate (2, BitsPerComputeUnit) -1; public static int [] mulitplyWithIntCarry (int a0, int b0, int BitsPerComputeUnit) { int a = Math.max(a0, b0); int b = Math.min(a0, b0); int Exp_MAX_VALUE =SumExperiment. powIterate (2, BitsPerComputeUnit) -1; if (a0<=0 || b0<=0 || Exp_MAX_VALUE/a >=b ) { return new int []{ a*b,0}; } // PART 1 int tmp1 = Exp_MAX_VALUE/a ; int M = Exp_MAX_VALUE; int k = tmp1 + 1;// int c = b/k; int r = b%k; int totalCarry = 0; int totalRemainder = 0; totalCarry = c; int r1 = ( a * (k-1) -M -1 + a ); if (c<=0 || r1<=0 || M/c >=r1 ) { int [] arr = SumExperiment.sumWithIntCarry (c * r1, a * r,BitsPerComputeUnit); if (arr [1] > 0) totalCarry += arr [1]; totalRemainder = arr [0]; } else { int [] arr = mulitplyWithIntCarry( c, r1,BitsPerComputeUnit); // carry won't overflow since a*b <= M^2 if (arr [1] > 0) totalCarry += arr [1]; totalRemainder = arr [0]; arr = SumExperiment.sumWithIntCarry (totalRemainder, a * r,BitsPerComputeUnit); if (arr [1] > 0) totalCarry += arr [1]; totalRemainder = arr[0]; } return new int []{ totalRemainder,totalCarry}; } public static void main(String[] args) { // System.out.println("Experiment 1 some reconnaissance to verify PART-1"); // int a = 2;// a greater than 1, but 1,0 are handled // int tmp1 = Exp_MAX_VALUE/a ; // int k = tmp1 + 1;// if a is 1, here is not safe. // System.out.println(k*a); // System.out.println((k-1)*a); System.out.println(SumExperiment.toIntArraySting( mulitplyWithIntCarry (4, 8,4) )); //[0,2]?! System.out.println(256*256/1024 +","+ (256*256)%1024); System.out.println(SumExperiment.toIntArraySting( mulitplyWithIntCarry (256, 256,10) )); //! System.out.println(537*429/1024 +","+ (537*429)%1024); System.out.println(SumExperiment.toIntArraySting( mulitplyWithIntCarry (537,429,10) )); //! System.out.println(SumExperiment.toIntArraySting( mulitplyWithIntCarry (Integer.MAX_VALUE /2, Integer.MAX_VALUE /3,31) )); //[1431655766,357913940] ?? } }