When dealing with code that utilizes large integers. That is, integers that are larger in size than the maximum your computer’s CPU supports, you should probably use the built-in math libraries.
But here is a simple “Big Num” Add and Multiply routine if you’re curious how one can be implemented using only integer math and string processing.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
<?php // Kervin Pierre // 2012-03-21 // // Simple PHP big num / arbituary precision integer add and multiply. // // Proof of concept. Use BC Math for real work // http://us3.php.net/manual/en/book.bc.php // // // Add two big integers function ba($a, $b) { if( $a === "0" ) return $b; else if( $b === "0") return $a; $aa = str_split(strrev(strlen($a)>1?ltrim($a,"0"):$a), 9); $bb = str_split(strrev(strlen($b)>1?ltrim($b,"0"):$b), 9); $rr = Array(); $maxC = max(Array(count($aa), count($bb))); $aa = array_pad(array_map("strrev", $aa),$maxC+1,"0"); $bb = array_pad(array_map("strrev", $bb),$maxC+1,"0"); for( $i=0; $i<=$maxC; $i++ ) { $t = str_pad((string) ($aa[$i] + $bb[$i]), 9, "0", STR_PAD_LEFT); if( strlen($t) > 9 ) { $aa[$i+1] = ba($aa[$i+1], substr($t,0,1)); $t = substr($t, 1); } array_unshift($rr, $t); } return implode($rr); } // Multiply two big integers function bm($a, $b) { if($a=="0"||$b=="0") return "0"; $res = "0"; $r = $a; for( $i=strlen($b)-1; $i>=0; $i--) { for( $j=0; $j<(int)($b[$i]); $j++) $res = ba($r, $res); $r .= "0"; } return $res; } $sum = "2"; $pow = 1024; for($i=0; $i<$pow-1; $i++) $sum = bm($sum, "2"); $str1 = trim($sum,"0"); echo "<br/>"; $str2 = (string) bcpow(2,$pow); if( strcmp($str1, $str2) !== 0) echo "error"; else { echo $str1 . "<br/>"; $sum2 = 0; for( $i=0; $i<strlen($str1); $i++) $sum2 += $str1[$i]; echo "Total = $sum2"; } ?> |
