PERL_MATHEMATICS
sub prime_factors {
# Requires is_prime func
my $n = shift;
my @factors = ();
if ($n % 2 == 0) {
push(@factors, 2);
}
my $d = 3;
while ($d <= sqrt($n)) {
if ($n % $d == 0) {
push(@factors, $d) if &is_prime( $d );
}
$d += 2;
}
return @factors;
}
sub nthroot ($$)
{
# Function: nthroot
# Description : Calculates nth root
# Input : root, base
# Output : nthroot
# Call as : print nthroot(5, 34), "\n";
# Notes : Does not edit parameters
my ( $n, $A ) = @_;
my $x0 = $A / $n;
my $m = $n - 1.0;
while(1) {
my $x1 = ($m * $x0 + $A / ($x0 ** $m)) / $n;
return $x1 if abs($x1 - $x0) < abs($x0 * 1e-9);
$x0 = $x1;
}
}
print nthroot(5, 34), "\n";
print nthroot(10, 7131.5 ** 10), "\n";
print nthroot(0.5, 7), "\n";
sub max2
{
my ($x1, $x2)= @_;
return $x1 > $x2? $x1 : $x2;
}
# 1st way - By calculating gcd
sub lcm {
# Function: lcm
# Description : Calculates least common multiple
# Input : number, number
# Output : lcm
# Usage : print lcm(3, 4);
# Notes : Using gcd inner function
sub gcd {
my ($a, $b) = @_;
while ($a) { ($a, $b) = ($b % $a, $a) }
$b
}
my ($a, $b) = @_;
($a && $b) and $a / gcd($a, $b) * $b or 0
}
print lcm(3, 4);
####################################################
# Second way - By repeatedly increasing smallest
sub lcm {
# Function : lcm
# Description : Calculates lcm (diff method)
# Input : number, number
# Output : lcm
# Usage : print lcm(1001, 221);
# Notes : Fastest
use integer;
my ($x, $y) = @_;
my ($a, $b) = @_;
while ($a != $b) {
($a, $b, $x, $y) = ($b, $a, $y, $x) if $a > $b;
$a = $b / $x * $x;
$a += $x if $a < $b;
}
$a
}
print lcm(1001, 221);
sub is_prime { # usage &is_prime( $n )
my $n = shift;
my $d=1;
if ($n == 2 || $n == 3) {
return 1;
}
if ($n % 2 == 0) {
return 0;
}
my $sqrt = sqrt( $n );
while ($d <= $sqrt) {
$d += 2;
return 0 if $n % $d == 0;
}
return 1;
}
# Recursive
sub gcd($$) {
# Function : gcd
# Description : Calculates gcd of two numbers
# Input : number 1, number 2
# Output : gcd
# Call as : print gcd(40,182);
# Notes : Calculates gcd recursively
my ($u, $v) = @_;
if ($v) {
return gcd($v, $u % $v);
} else {
return abs($u);
}
}
print gcd(40,182);
#######################################
# Iterative
sub gcd_iter($$) {
# Function : gcd_iter
# Description : Calculates gcd iteratively
# Input : number 1, number 2
# Output : gcd
# Call as : print gcd_iter(40,182);
# Notes : Calculates gcd iteratively
my ($u, $v) = @_;
while ($v) {
($u, $v) = ($v, $u % $v);
}
return abs($u);
}
########################################
# Binary Iterative
sub gcd_bin($$) {
# Function : gcd_bin
# Description : Calculates gcd binary iterative
# Input : number1, number 2
# Output : gcd
# Call as : print gcd_bin(40,182);
# Notes : Fastest way
my ($u, $v) = @_;
$u = abs($u);
$v = abs($v);
if ($u < $v) {
($u, $v) = ($v, $u);
}
if ($v == 0) {
return $u;
}
my $k = 1;
while ($u & 1 == 0 && $v & 1 == 0) {
$u >>= 1;
$v >>= 1;
$k <<= 1;
}
my $t = ($u & 1) ? -$v : $u;
while ($t) {
while ($t & 1 == 0) {
$t >>= 1;
}
if ($t > 0) {
$u = $t;
} else {
$v = -$t;
}
$t = $u - $v;
}
return $u * $k;
}
#!/usr/bin/perl
# your code goes here
sub factors { ## produces array of factors, in ascending order
my($x) = @_;
my(@factors) = ();
my($d) = 2;
until ($d > sqrt($x)) {
if ($x % $d == 0) {
push(@factors, $d);
$x = $x/$d;
}
else {
$d += 1;
}
}
push(@factors,$x);
return @factors;
}
print factors(12);
sub distinct_factors { # produces list of _distinct_ factors
my($x) = shift;
my(@factors) = ();
my($d) = 2;
until ($x == 1) {
if ($x % $d == 0) {
push(@factors, $d);
$x /= $d;
while ( $x % $d == 0 ) {
$x /= $d;
}
}
else {
$d += 1;
}
}
return @factors;
}
1. nthroot.pl : Calculates ninth root of a number
2. gcd.pl : Algorithms to calculate greatest common divisor
3. lcm.pl : Algorithms to calculate least common multiple
4. is_prime : Check if parameter is prime, returns T/F
5. prime_factors : Returns ONLY prime factors of number
6. distinct_factors : Returns all factors of a number
7. factors : Returns smallest factors of a number
8. factorial : Calculates factorial of a number
9. binomial_coeff : Calculates binomial coefficient
10. max2 : Returns maximum of two numbers
11. min2 : Returns minimum of two numbers
sub min2
{
my ($x1, $x2)= @_;
return $x1 < $x2? $x1 : $x2;
}
sub factorial { ## only for small...?
my($n) = @_;
my($out) = 1;
for ($i=1; $i<=$n; $i++) {
$out *= $i;
}
return $out;
}
print factorial(4);
sub binomial_coefficient {
my($n,$k) = @_;
my($out) = 1;
for ($i=$n; $i>$n-$k; $i--) {
$out *= $i;
$out /= $n-$i+1;
}
return $out;
}
print binomial_coefficient(35,7);