A More Powerful Exponential Function

In this post I describe how I solved the following question (from Chapter 3 of OCaml from the very beginning):

Use pattern matching to write a function which, given two numbers x and n, computes x to the power of n.

Although the author provided an answer, his function returns a stack overflow error when n is negative.  Also, his function is of type int.  Because the specification only requires x and n to be numbers, not positive integers, I feel the need to make a function that is closer to the specification.

Running a standalone program

I’d like to put this on my github, so I skipped ahead to Chapter 16 of the book and learnt just enough to move away from the interactive prompt environment.

To build programs, one should abstract sets of types and functions into modules:
  • To build a module, save your code in a .ml file.  OCaml programs live in files with lowercase names ending in .ml.
  • Start your module with a comment explaining the module.  Comments are written between (* and *).
  • Run ocamlc (filename).ml in a terminal to compile your program into an executable pre-compiled module.  You will see the executable in your current directory, with the same file name but ending in .cmo.
  • Run load “(filename).cmo”;; in the OCaml prompt to load the pre-compiled module into OCaml.  Oops, when I ran this to my file, it returned Error: Unbound value load.  It seems the book is too outdated and load isn’t a command anymore.

Function power_int: int -> int -> int

I turned to more updated references, e.g., the official OCaml manual or the Real World OCaml book.  Following section 1.9 of the manual, I ran the following in the directory my file was in:

ocamlc -o power_int power_int.ml

I use the same command ocamlc as above, but I specific the output file name with ‘-o‘ to be power_int.  I tested my program by running:

./power_int 5 2

and it returns 25.  Yay!  It works with positive integers!  Well, by integers I mean integers within the range min_int and max_int, not the mathematical definition, which are not bounded.  What about negative integers?  When x is negative, it works just fine:

./power_int -5 3

returns -125, as it should.  When n is negative, it returns 0 in all the cases I examined.  This is because the function evaluates to type int, which means that when the value is a non-integer, it rounds to the closest integer that is closest to zero.  So it makes sense that 2 to the power of -1 rounds to 0, and -2 to the power of -1 rounds to 0, etc.  However, that’s not informative.  Time to fix it.

Function power_float: float -> float -> float

Converting to the type float, which stands for floating point numbers, fixes two things.  First, the program can now take in any number for x (well, again, within the min_float and max_float range of course) instead of integers.  Of course, n still has to be integers because of how I recurse the function.  Second, the program now returns a floating point number when n is negative.  Although not perfect, this function is much closer to what was asked.

To write power_float, I revised power_int by telling OCaml that the arguments are in float with the float operators.  The float operators have a ‘.’ to the right of the int operators.  E.g., +., -., etc.  Make sure to match all operators and operands that an operand interacts with to type float, otherwise there will be a type error.

What is 0^0?

Both my programs return 1 when both x and n are zero.  This is true for a few programming languages, but not all.  Some returns undefined.  As always, it’s a good idea to check all the boundary cases before proceeding.

Go ahead and test my program!  It works!  Yay!

Edit: I added a fast exponential version on github!  Check it out!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.