onlyforbopi
1/4/2017 - 7:33 AM

PERL_MATHEMATICS

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);