## Sunday, August 05, 2007

### Number Theory

Today I released a collection of number theory functions through PLaneT.

The code began as an experiment. I grabbed a book on number theory from the shelve ("Elementary Number Theory" by Gareth A. Jones and J. Mary Jones) and began illustrating each definition and each theorem with Scheme code. The first half of the source code is thus a well commented mix of definitions, theorems and code.

The second half contains more sophisticated algorithms mostly from the excellent book "Modern Computer Algebra" by Joachim von zur Gathen and Jürgen Gerhard. The algorithms for factorizing large integers come from this book.

Finally there are some definitions of special functions, mostly inspired by the problems of the Euler Project. The revival of the code is due to the Euler Project, which is a collection of small problems of very varying difficulty. The tools I have used to solve the problems (apart from the number theory library) are David Herman's memoize package (don't forget to use memoize* when working with numbers) and the eager comprehensions from srfi 42.

The documentation of the number theory library lists all the available functions.

Please write with bugs, suggestions, and improvements.

offby1 said...

I just glanced at it, and I'm impressed: you wrote "with-modulus" without having to create a new "language" to replace "mzscheme". I'd done exactly that when I made my own version, but I -wanted- to do it your way; I just didn't know how.

01:34
Rasser said...

Jeg så din side via reddit. Jeg er ulvund på project euler.

01:21
V said...

I tried using your library, but it says "compile: unbound variable in module in: integer-length". Did you use integer-length as defined in SRFI 60?

00:30
Jens Axel Søgaard said...

Hi V,

Which version of PLT Scheme are you using? In the current version of PLT Scheme (version 371) integer-length is a primtive and part of mzscheme.

Example:

> (require (planet "math.ss" ("soegaard" "math.plt")))
> (prime? 13)
#t

00:37
navaburo said...

This semester I am taking a number theory course using Jones and have been implementing algorithms in Scheme as we go along.

Then I ran into your code!

Very cool, thanks. I will use it and report any issues!

01:06
Tim said...

Two things:
First, I'm using PLT Scheme 4.02, and when I require math.ss 1.2 from PLaneT I get an error that 'reverse!' is an unbound variable. It's only used in 'farey'. I think you just need to require srfi/1 to remove this error.
Second, I've written a simple in-primes sequence (similar to in-naturals) using math.ss. There seems to be nothing similar in the package repository; would you like to include it in math.ss?

01:25