|
|
|
|
|
|
| |
Inspired by the recent work of Jeremy Watts, I decided to write a code segment for multiplying large integers, which may be used, eventually, to factorize numbers or simply to supplement the inadequacy of the pocket calculators. Note that in Unix, there is a utility called dc that will do arithmetic for large numbers, but you cannot easily 'port' it to your PHP routines.
I have always been fascinated by big-number arithmetic, this has been a programming exercise for myself, in fact, my first ever program written in PHP. If you have comments, positive or negative, feel free to post them. I am here to listen to you and learn from the gurus.
| <html>
<head>
<title>Multiplication of big numbers</title>
<?php
function BigMult($N1,$N2){
// Count digits for each number, and the total
$n1=strlen($N1); $n2=strlen($N2); $nn=$n1+$n2;
// Put each in an array, $a1[0] is the right most digit of the first number, etc.
$a1=array();
for($i=$n1-1;$i>=0;$i--){
$a1[]=intval(substr($N1,$i,1));
}
$a2=array();
for($i=$n2-1;$i>=0;$i--){
$a2[]=intval(substr($N2,$i,1));
}
// prepare empty string for result
$result="";$carry=0;
// calculations
for($i=0;$i<=$nn-2;$i++){ // loop through each digit of result
$j1=$i;
if($j1>$n1-1)$j1=$n1-1;
$sum=$carry;
for($j=$j1;$j>=0;$j--){ // $j, $k are indices of each pair of digits
$k=$i-$j;
if($k>=0&&$k<=$n2-1){
$sum+=$a1[$j]*$a2[$k];
}
}
// add right-most digit to result, the rest carried
$digit=$sum%10;
$carry=($sum-$digit)/10;
$digit=(string)$digit;
$result=$digit.$result; // add new digit to the left
}
if($carry!=0)$result=(string)$carry.$result; // last carry
return $result;
}
?>
</head>
<body>
<?PHP
$m1="898945894598459889589345"; $m2="8498739018791873190879123874391287019834173489273498";
$product=BigMult($m1,$m2);
printf("N1 = %s<br>N2 = %s<br>PRODUCT = %s<br>", $m1, $m2, $product);
?>
</body>
</html> | |
|
|
| 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. | |
| | | | jeremy watts wrote : 1096
Hi CP, Yours looks shorter than mine too! Havent tested it yet, how does it perform? I should have big_divide done soon by the way and also have a factorisation routine planned for large integers
| | | | P C wrote : 1097
Jeremy,
Thanks for visiting. In fact, I forgot to give the details of the multiplication. Here they are:
1. The digits have been transformed to integers until the resulting digits were obtained, then they are converted back to string for display.
2. The calculation is done digit by digit of the result, starting from the right. For example, to multiply 1234 by 4567,
right most digit=4*7=(2)8, with a carry of 2
next digit=7*3+4*6+carry=(4)7, carry=4
next digit=7*2+6*3+5*4+carry=(5)6, carry=5, and so on.
I look forward to your division program. If you want to do square roots, I have an excellent algorithm.
On the other hand, there are standard php routines that handle `arbitrary precision` arithmetic called bcmath. The routines are similar to what we wrote, except that they take care of floating point numbers as well. I have not tried them out yet. Some sites do not activate them. The routines would be named bcadd(...), bcmult(...), bcmod(...) and the like. You could use them to check your results.
Happy programming!
| | | | John Gunners wrote :1099
Hi Jeremy Watts
Wonder if you could help me with a script. I have to make a php script for checking if a company number is valid. My company number is:983153968 the last number (8)is a checking digit and the program should be based on a so called modulus 11. So if a customer wants to registrer as a customer in my webpage the customer has to identify himself with this number. Here is how it works:
The modulus number are 32765432. So if i want to check a BID like mine eks. BID number 983153968. The last digit "8" in my BID number is the(check number).
So if i want to check if my number is coorect i have to multiply each digit in the modulus number and my BID, like this (from the left to the right.: (3*9)+(2*8)+(7*3)+(6*1) and so on... and the sum of the products will be 146. The sum is divided by 11=143 and a reminder of 3. Finally i have to substract 3 from 11, and i get my check number "8".
The following rules have to be meet:
1. If the reminader is "0" then the controll digit will be "0"
2. If the controll digit is =< 10 its not valid.
Can you please help me with a php scrips to pur right in to mys php webpage code ? iam not a script programmer myself, iam started a week ago learning php, lol.
| |
|
|
|
