System.out.println(Integer.MAX_VALUE); // The following lines caused an overflow, but no trace shown for its // happening. System.out.println(Integer.MAX_VALUE * Integer.MAX_VALUE); System.out.println(Integer.MAX_VALUE * 2); System.out.println(Integer.MAX_VALUE + 1); // The following lines provide us some hints about how to handle // overflow. System.out.println("99*99 = " + 99 * 99); System.out.println("99 99*99 = " + 9999 * 99); System.out.println("9900*99 = " + 9900 * 99); System.out.println("9900*99 + 99*99= " + (9900 * 99 + 99 * 99)); System.out.println("9999*9999 = " + (9999 * 9999)); // // Output: // 2147483647 // 1 // -2 // -2147483648 // 99*99 = 9801 // 99 99*99 = 989901 // 9900*99 = 980100 // 9900*99 + 99*99= 989901 // 9999*9999 = 99980001

For most engineering students even of computer science or physics, the first year college study will involve designing an addition circuit using logical gates on a breadboard. One point we should recall is that the results will not be a single bit while we try to sum up two single bits as the different operands. The result would need a bit represent the sum, another bit called carry. In later year, I remember probably (I read the book, not formally take about 8086 CPU) in an assembly language book, the sum results of two registers will be saved in a register (maybe one of the above), if there is an overflow, a register or a bit of some register will indicate there is a carry and store the carry. However, this was a post-mortem approach. You can only regret it, but no-way to reverse it. It is uncertain if most up-to-date software checks the carry (read the above-mentioned register) and set a proper exception handle etc.

This is rather a motivation than a problem. I took a couple of days figure out a way to avoid the problem at the same time practice some healthy software development methodology.

I.The mathematical condition for sum overflow:
A + B > M <=> M - A < B. The right hand side operation will not cause an overflow, but the left hand side may cause an overflow. A and B are the sum operands and unsigned integers. M is the max value below overflow.

II.The mathematical condition for multiplication overflow:
A and B are the multiplication operands and unsigned integers. If A is equal to 0, there will not be overflow. Otherwise, A * B > M <=> M / A < B. M is the max value below overflow. Similarly, the RHS of the equivalence formula is overflow safe.

System requirement:
JDK1.7 or higher, Maven 3.0 or higher installed Preferably, a Java IDE that can import Maven project.

Download and unpack the source, for Windows users, you can consider 7zip for the tar.gz file. In a Linux/UNIX shell, or Cygwin etc:
Md5sum: d42cd96160d2e0b9244f75d67db12bff PreemptiveOverflowPrevention.tar.gz
wget http://www.heteroclinic.net/attached/PreemptiveOverflowPrevention.tar.gz tar -xvzf PreemptiveOverflowPrevention.tar.gz

Build the jar binary and generate the coverage report ( target/site/jacoco-ut/index.html):
cd PreemptiveOverflowPrevention mvn clean package

Use the following command to generate Javadoc ( target/site/apidocs/index.html):
mvn javadoc:javadoc

<!-- /* * 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 (third party licenses 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 liablity 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. * * Apache License 2.0 applied for Maven configuration (and others if applicable). * Please refer to the following link for Maven Jacoco code coverage report setting, Maven profiles setting etc. * http://www.petrikainulainen.net/programming/maven/creating-code-coverage-reports-for-unit-and-integration-tests-with-the-jacoco-maven-plugin/ * */ -->

/* * 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] ?? } }