|
|
|
|
|
|
| |
this is a 'highest common factor' (or 'greatest common divisor' ) and 'lowest common multiple' finder for large integers. The other procedures like 'big_divide' must be included with the function 'big_gcdlcm' for the whole thing to work.
not sure of the limit of the thing - maybe someone could find out. :)
| <?php
$number_one = "12775648998764099886699889456457657955647643";
$number_two = "7200894578987876876587687676576";
list($gcd, $lcm) = gcdlcm ($number_one, $number_two);
print $gcd;
print "<br>";
print $lcm;
function gcdlcm ($number_one, $number_two) {
$gcd = "";
if (($number_one == "0") or ($number_two == "0")) {
$gcd = "1";
return $gcd;
}
else {
$test = big_subtract($number_one, $number_two);
if ($test[0] == "-") {
$buffer = $number_one;
$number_one = $number_two;
$number_two = $buffer;
}
$dividend = $number_one;
$divisor = $number_two;
$remainder = $dividend;
while ($remainder[0] != "0") {
list($quotient, $remainder) = big_divide($dividend, $divisor);
$gcd = $divisor;
$dividend = $divisor;
$divisor = $remainder;
}
}
$product = big_multiply($number_one, $number_two);
list($quotient, $remainder) = big_divide($product, $gcd);
$lcm = $quotient;
return array($gcd, $lcm);
}
function big_divide($dividend, $divisor) {
$test = "";
$quotient_string = "";
$remainder = "";
$old_section = "";
$section = "";
$index = 0;
if ($divisor == "0") {
$quotient = "";
$quotient = "error";
$remainder = "error";
return array($quotient, $remainder);
}
$test = big_subtract($dividend, $divisor);
if ($test == "0") {
$quotient = "";
$quotient = "1";
$remainder = "0";
return array($quotient, $remainder);
}
if ($test[0] == "-") {
$quotient = "";
$quotient = "0";
$remainder = $dividend;
return array($quotient, $remainder);
}
while ($index < (strlen($dividend))) {
$section = $section . $dividend[$index];
if ($section[0] == "0") {
$flag = 0;
$index_two = 0;
while (($flag == 0) && ($index_two < strlen($section))){
if ($section[$index_two] == "0") {
$index_two++;
}
else {
$flag = 1;
}
}
$section = substr($section, $index_two);
}
$test = big_subtract($section, $divisor);
if ($test[0] != "-") {
$flag = 0;
$quotient = 0;
while ($flag == 0) {
$test = big_subtract($section, $divisor);
if ($test[0] == "-") {
$flag = 1;
}
else {
$section = $test;
$old_section = $section;
$quotient++;
}
}
$quotient = (string)$quotient;
$remainder = $old_section;
$quotient_string = $quotient_string . $quotient;
$section = $remainder;
}
else {
$quotient_string = $quotient_string . "0";
}
$index++;
}
if ($section == "") {
$section = "0";
}
$flag = 0;
$index = 0;
while ($flag != 1) {
if ($quotient_string[$index] == "0") {
$index++;
}
else {
$flag = 1;
}
}
$quotient_string = substr($quotient_string, $index);
$quotient = "";
$quotient = $quotient_string;
$remainder = $section;
return array($quotient, $remainder);
}
function big_multiply ($number_one, $number_two) {
$length_one = strlen($number_one);
$length_two = strlen($number_two);
$row = "";
$digit_string = "";
$answer = "";
$zero_number = 0;
$carry = 0;
for ( $index_two = ($length_two - 1); $index_two >= 0; $index_two-- ) {
$zero_string = "";
for ( $index = 1; $index <= $zero_number; $index++ ) {
$zero_string = $zero_string . "0";
}
for ( $index_one = ($length_one - 1); $index_one >= 0; $index_one-- ) {
$digit = ((( integer ) $number_two[$index_two]) * (( integer ) $number_one[$index_one])) + $carry;
$digit_string = ( string ) $digit;
if ($digit >= 10) {
$row = $row . $digit_string[1];
$carry = ( integer ) $digit_string[0];
}
else {
$row = $row . $digit_string;
$carry = 0;
}
}
if ($carry != 0) {
$row = $row . ( string ) $carry;
}
$row = $zero_string . $row;
$row = strrev($row);
$answer = big_addition ($answer, $row);
$row = "";
$carry = 0;
$zero_number++;
}
$flag = 0;
$length = strlen($answer);
for ( $index = 0; $index <= ($length - 1); $index++ ) {
if ($answer[$index] != "0") {
$flag = 1;
}
}
if ($flag == 0) {
$answer = "0";
}
return $answer;
}
function big_addition ($number_one, $number_two) {
if (strlen($number_one) > strlen($number_two)) {
$longer_length = strlen($number_one);
$shorter_length = strlen($number_two);
$set_one = $number_one;
$zero_number = ($longer_length - $shorter_length);
$zero_string = "";
for ( $index = 1; $index <= $zero_number; $index++ ) {
$zero_string = $zero_string . "0";
}
$set_two = $zero_string . $number_two;
$length = strlen($number_one);
}
if (strlen($number_one) < strlen($number_two)) {
$longer_length = strlen($number_two);
$shorter_length = strlen($number_one);
$set_two = $number_two;
$zero_number = ($longer_length - $shorter_length);
$zero_string = "";
for ( $index = 1; $index <= $zero_number; $index++ ) {
$zero_string = $zero_string . "0";
}
$set_one = $zero_string . $number_one;
$length = strlen($number_two);
}
if (strlen($number_one) == strlen($number_two)) {
$set_one = $number_one;
$set_two = $number_two;
$length = strlen($number_one);
}
$carry = 0;
$answer = "";
for ( $index = ($length - 1); $index >= 0; $index-- ) {
$digit = $carry + (( integer ) $set_one[$index]) + (( integer ) $set_two[$index]);
$digit_string = (( string ) $digit);
if ($digit >= 10) {
$answer = $answer . $digit_string[1];
$carry = ( integer ) $digit_string[0];
}
else {
$answer = $answer . $digit_string;
$carry = 0;
}
}
if ($carry != 0) {
$carry_string = (( string ) $carry);
$answer = $answer . $carry_string;
}
$answer = strrev($answer);
return $answer;
}
function big_subtract ($number_one, $number_two) {
$answer = "";
$sign = "";
if (strlen($number_one) > strlen($number_two)) {
$longer_length = strlen($number_one);
$shorter_length = strlen($number_two);
$set_one = $number_one;
$zero_number = ($longer_length - $shorter_length);
$zero_string = "";
for ( $index = 1; $index <= $zero_number; $index++ ) {
$zero_string = $zero_string . "0";
}
$set_two = $zero_string . $number_two;
$length = strlen($number_one);
$sign = "";
}
if (strlen($number_one) < strlen($number_two)) {
$longer_length = strlen($number_two);
$shorter_length = strlen($number_one);
$set_one = $number_two;
$zero_number = ($longer_length - $shorter_length);
$zero_string = "";
for ( $index = 1; $index <= $zero_number; $index++ ) {
$zero_string = $zero_string . "0";
}
$set_two = $zero_string . $number_one;
$length = strlen($number_two);
$sign = "-";
}
if (strlen($number_one) == strlen($number_two)) {
$length = strlen($number_one);
$flag = 0;
$index = 0;
while (($flag == 0) && ($index <= ($length - 1))) {
if ((( integer ) $number_one[$index]) > (( integer ) $number_two[$index])) {
$set_one = $number_one;
$set_two = $number_two;
$sign = "";
$flag = 1;
}
if ((( integer ) $number_one[$index]) < (( integer ) $number_two[$index])) {
$set_one = $number_two;
$set_two = $number_one;
$sign = "-";
$flag = 1;
}
if ((( integer ) $number_one[$index]) == (( integer ) $number_two[$index])) {
$index++;
}
}
}
if (strlen($number_one) == strlen($number_two)) {
$flag = 0;
for ( $index = 0; $index <= ($length - 1); $index++ ) {
if ($number_one[$index] != $number_two[$index]) {
$flag = 1;
}
}
if ($flag == 0) {
$answer = 0;
return $answer;
}
}
$carry = 0;
$answer = "";
for ( $index = ($length - 1); $index >= 0; $index-- ) {
$digit = $carry + (( integer ) $set_one[$index]) - (( integer ) $set_two[$index]);
if ($digit < 0) {
$digit = $digit + 10;
$carry = -1;
$answer = $answer . (( string ) $digit);
}
else {
$answer = $answer . (( string ) $digit);
$carry = 0;
}
}
$answer = strrev($answer);
$flag = 0;
$length = strlen($answer);
$index = 0;
while (($flag == 0) && ($index <= ($length - 1))) {
if ($answer[$index] != "0") {
$flag = 1;
}
$index++;
}
$begin = $index - 1;
$result = "";
for ( $index = $begin; $index <= ($length - 1); $index++ ) {
$result = $result . $answer[$index];
}
$answer = $sign . $result;
return $answer;
}
?> | |
|
|
| Math operations on big numbers
Categories : PHP, Math. | | | Latitude-Longitude to Miles
Categories : PHP, Utilities, Math. | | | Weighted Random - Random Scripts usually chose one out of each item, and each item have an equal chance to be chosen. But what if you want an item to be chosed more frequently than other?
Categories : PHP, Math., Arrays | | | Diffusion-Limited Aggregation visualization
Categories : PHP, Graphics, Algorithms, Math. | | | Temperature Conversion
Categories : PHP, Math., Beginner Guides | | | decoct -- Decimal to octal
Categories : PHP, PHP Functions, Math. | | | How to judge if an integer is odd or is even in Php3?
Categories : Math., PHP, Algorithms | | | Calculator for Baroque Violin strings
Categories : Math., PHP, Strings | | | Show the steps for converting a number from a given base to base 10. Shows the steps involved in converting a number from a given base to base 10.
Categories : PHP, Math., Algorithms | | | Query2Report : Generating Html, Pdf and Csv Reports from SQL Query
Categories : PHP, PHP, HTML, PDF, Excel | | | 3dLib - a class for drawing in 3D space. Supported functions: Line, SetPixel, Polygon, FilledPolygon, etc. 3dChart() function has been added for one-call drawing of 3d charts. Support of mostly used 3d-transformations.
Categories : Graphics, Math., PHP Classes, PHP, Charts and Graphs | | | Easy to use random number function that seeds with uniqid and allows a max value
Categories : Math., PHP | | | Arbitrary Precision Math using BCMATH routines
Categories : PHP, Math., BC math | | | Greatest Common Denominator - A simple class that finds the greatest common denominator for two integers.
Categories : PHP, PHP Classes, Math. | | | Prime number finder (Sieve of Erastothenes)
Categories : PHP, Algorithms, Math. | |
|
|
|
