Re: [seul-edu] Programming Mathematics

[Roger Dingledine <arma@mit.edu>]

I'll answer some of these in perl, as sparetime fun programming things.
But remember that the motto of perl is 'there's more than one way to
do it'. So only post optimizations if they are substantially better
(faster and more readable) than my code. ;) (And I reserve the right to
kill this thread if it gets too pedantic.)
(I didn't deal with some end-cases. So these snippets aren't as robust
as they could be.)

On Mon, Sep 25, 2000 at 07:34:26AM -0700, lp wrote:
>   A program that does a loop and prints the numbers from 1 to 10.

for $i (1..10) {
  print "$i\n";
}

>   A program that computes a factorial using recursion.

sub factorial {
  my ($val) = @_;

  return(1) if $val<2;

  return($val * factorial($val-1));
}

>   A program that prints an addition table,

(What's an addition table?)

for $i (1..10) {
  print "$x+$i is " . $x+$i . "\n";
}

>   A program that prints a multiplication table,

for $i (1..10) {
  print "$x*$i is " . $x*$i . "\n";
}

>   A program that prints a multiplication table mod n.

sub multmodn {
  my ($x, $n) = @_;
  for $i (1..10) {
    print "$x*$i (mod $n) is " . $x*$i % $n . "\n";
  }
}

>   A program that prints the sum of two squares.

sub squareandadd {
  my ($a, $b) = @_;

  print $a**2 + $b**2; # don't use ^, that's a bitwise operator
}

>   A program that inputs b,n, and p and prints b^n mod p
>     for n=1 to n-1.

# doing expmod for all 1..n-1 probably has some slicker optimizations
# since you're computing all the values. hum.

# this is equivalent to print (($b**$n)%$p), but that's cheating ;)
# (and perl rounds that off badly, so hey)
# (unless there's a bug in my code. is there?)
sub expmod { # print b^n (mod p)
  my ($b, $n, $p) = @_;

  if($n<2) {
    return ($b % $p);
  }

  if($n&1) { # n is odd
    return((expmod($b,$n-1,$p) * $b) % $p);
  }

  # n is even
  return((expmod($b,$n/2,$p) ** 2) % $p);
}

for $i (1..10) { # or (1..$n)
  print "expmod(3,$i,105) = " . expmod(3,$i,105) . "\n\n";
}

>   A program that generates a list of prime numbers and prints
>     the results to a file.

sub is_prime {
  my ($num) = @_;
  my $i;

  return(0) if ($num==1); # special case
  return(0) if ($num % 2 == 0 and $num != 2); # even and not 2

  for($i=3;$i<int(sqrt($num))+1;$i+=2) {
    return(0) if ($num % $i == 0); # it's a factor
  }
  return(1);
}


sub print_primes_to_file {
  open(F,">yourfile") or die "can't open yourfile for writing";
  for $i (1..100) {
    print F "$i\n" if is_prime($i);
  }
  close(F);
}

>   A program that factors a number.

sub print_factors {
  my ($num) = @_;
  my $i;

  return if($num<2); # this means it mistakenly claims 1 has no factors. ho hum.

  for($i=2;$num % $i;$i++) {} # count up to the first factor

  print "$i\n";

  return if($i==$num); # it's prime, no more factors

  print_factors($num / $i); # tail recurse
}

>   A program that reads a list of numbers from a file and prints their
>     factors.

# give it the filename as an argument. one number per line in file.
while(<>) {
  chomp; # pull off the whitespace from the end of the line.
         # you probably don't even need this.
  print "\n\n$_:\n";
  print_factors($_);
}

hope this helps. only expmod, is_prime, and print_factors are remotely
publishable... the rest is just glue.
--roger