Happy new year everyone! I wrote this sub yesterday. The goal here is to perform a division with a big positive integer dividend that can be any length. Currently, this sub cannot divide two big integers. It can only divide a big integer by one digit or multiples of 10 or if the dividend and divisor are less than 16 digits. Can anyone show me how you would write BIGDIV sub that takes two big positive integers of any size? That's next on my todo list :-D
#
# This function performs simple divisions on big positive integers
# in base 10 if ONE of the following three conditions is true:
#
# * Divisor is 1 digit long (Dividend can be any length)
# * Divisor is a multiple of 10 (Dividend can be any length)
# * Dividend and divisor are both 15 digits or less
#
# The 1st argument should be the dividend, the 2nd the divisor.
# The 1st return value is the quotient followed by the remainder.
#
# Usage: LIST = BIGDIVN(BIGINT, DIGIT)
#
sub BIGDIVN
{
defined $_[0] && defined $_[1] or return (0, 0);
my $A = $_[0]; $A =~ tr|0-9||cd; # Remove illegal chars
my $B = $_[1]; $B =~ tr|0-9||cd; # Remove illegal chars
$A =~ s/^0+(.+)/$1/; # Remove preceding zeros
$B =~ s/^0+(.+)/$1/; # Remove preceding zeros
length($A) && $B or return (0, 0); # Divide by zero?
$B eq '1' and return ($A, 0); # Divide by one?
if ($B =~ m/^1(0+)$/) # Divide by 1, 10, 100, 1000...?
{
my $Z = length($1);
length($A) <= $Z and return (0, $A);
my $Q = substr($A, 0, length($A) - $Z);
my $R = substr($A, -$Z);
$Q =~ s/^0+(.+)/$1/; # Remove preceding zeros from quotient
$R =~ s/^0+(.+)/$1/; # Remove preceding zeros from remainder
return ($Q, $R);
}
elsif (length($A) < 16 && length($B) < 16) # Divide small numbers
{ return (int($A / $B), $A % $B); }
elsif (length($B) != 1)
{ return (0, 0); } # We only accept simple divisons
# + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
# Okay, here we're going to divide a big integer by a single digit.
# First, we create lookup tables for processing big integers.
# These lookup tables are necessary, so we can completely
# avoid doing divisions or multiplications.
# The first lookup table ($LUT) is for finding the quotient.
# When dividing any 1-digit or 2-digit number by the divisor,
# the result is going to be found in $LUT.
# The second lookup table ($MUL) is a multiplication table
# in which each byte is a product of the divisor going
# from 0 to 9. So, if we're dividing by 6, then $MUL is going to
# hold the following: "\0\6\x0B\x12\x1B\x1E\x24\x2A\x30\x36"
my $S = 0; # Holds the previous multiplication's result
my $i = -1; # Counter goes from 0 to 9
my $LUT = ''; # Lookup table #1
my $MUL = ''; # Lookup table #2
while (++$i < 10)
{
$MUL .= chr($S); # Build lookup tables...
$LUT .= chr($i) x $B;
$S += $B;
}
$A =~ tr|0-9|\x00-\x09|; # Subtract 48 from dividend's digits
my $OUTPUT = ''; # This will hold the quotient
my $REM = 0; # This will hold the remainder
my $Q; # Current digit of the quotient
$i = -1; # Counter used to read digits from dividend
while (++$i < length($A))
{
$S = $REM . vec($A, $i, 8); # Merge remainder with current digit
$Q = vec($LUT, $S, 8); # Calculate next digit for quotient
$REM = $S - vec($MUL, $Q, 8); # Calculate remainder
$OUTPUT .= $Q;
}
$OUTPUT =~ s/^0+(.+)/$1/; # Remove preceding zeros from quotient
return ($OUTPUT, $REM);
}
sub __Test_BIGDIVN
{
return RunTest(
'BIGDIVN(0, 0)', '0 0',
'BIGDIVN(0, 10000)', '0 0',
'BIGDIVN(2179014949932, 3)', '726338316644 0',
'BIGDIVN(2179014949933, 3)', '726338316644 1',
'BIGDIVN(2179014949934, 3)', '726338316644 2',
'BIGDIVN(2179014949935, 3)', '726338316645 0',
'BIGDIVN(2179014949936, 3)', '726338316645 1',
'BIGDIVN(2179014949930, 5)', '435802989986 0',
'BIGDIVN(2179014949931, 5)', '435802989986 1',
'BIGDIVN(2179014949932, 5)', '435802989986 2',
'BIGDIVN(2179014949933, 5)', '435802989986 3',
'BIGDIVN(2179014949934, 5)', '435802989986 4',
'BIGDIVN(2179014949935, 5)', '435802989987 0',
'BIGDIVN(2179014949936, 5)', '435802989987 1',
'BIGDIVN("591092491992919449491", "0")', '0 0',
'BIGDIVN("18474690051828881094465", 3)', '6158230017276293698155 0'
+,
'BIGDIVN("18474690051828881094466", 3)', '6158230017276293698155 1'
+,
'BIGDIVN("18474690051828881094467", 3)', '6158230017276293698155 2'
+,
'BIGDIVN("18474690051828881094468", 3)', '6158230017276293698156 0'
+,
'BIGDIVN("18474690051828881094469", 3)', '6158230017276293698156 1'
+,
'BIGDIVN("18474690051828881094470", 3)', '6158230017276293698156 2'
+,
'BIGDIVN("18474690051828881094465", 5)', '3694938010365776218893 0'
+,
'BIGDIVN("18474690051828881094466", 5)', '3694938010365776218893 1'
+,
'BIGDIVN("18474690051828881094467", 5)', '3694938010365776218893 2'
+,
'BIGDIVN("18474690051828881094468", 5)', '3694938010365776218893 3'
+,
'BIGDIVN("59109249199291944949881", 8)', '7388656149911493118735 1'
+,
'BIGDIVN("59109249199291944949881", "1")',
+ '59109249199291944949881 0',
'BIGDIVN("59109249199291944949881", "100000000000000000")',
+ '591092 49199291944949881',
'BIGDIVN("59109249199291944949881", "10000000000000000000000000")',
+ '0 59109249199291944949881',
'BIGDIVN("50000000000000000000000", "1000000000000000")',
+ '50000000 0',
);
}
sub RunTest
{
@_ or return 1;
my $TESTS = @_ >> 1;
my $ERRORS = 0;
my $PTR = 0;
my $SUBNAME = ($_[0] =~ m/([a-zA-Z0-9]+)\(/) ? $1 : '';
for (my $i = 1; $i <= $TESTS; $i++)
{
my $CODE = $_[$PTR++];
my $CORRECT = $_[$PTR++];
my @RETURN = eval($CODE);
my $RETCOUNT = @RETURN;
foreach (@RETURN) { defined $_ or $_ = '<undef>'; }
my $OUTPUT = join(' ', @RETURN);
if ($OUTPUT ne $CORRECT)
{
$ERRORS++;
print "\n", '-' x 78,
"\nERROR #$ERRORS IN TEST $i: $CODE => |$OUTPUT| RetCount:
+$RETCOUNT",
"\n\n Correct: |$CORRECT|\n";
}
}
print( ($ERRORS) ? "\nFAIL - $SUBNAME() with $ERRORS errors." : "\nO
+K - $SUBNAME()");
return ($ERRORS) ? 0 : 1;
}
__Test_BIGDIVN();
