FactHacks

The FactHacks code snippets use Sage, a mathematical front-end to Python. The big advantage of Sage over Python is that it has many built-in math libraries.

The algorithms we discuss are built from simple arithmetic operations such as addition, subtraction, multiplication, division, etc. Our goal in each code snippet is for the reader to understand the sequence of arithmetic operations in the algorithm. There are many ways to speed up the code without changing the sequence of operations: Python and Sage often use unnecessarily slow methods to perform these arithmetic operations, and often impose severe overheads beyond the arithmetic operations. The simplest way to save time, without changing programming language, is to use Sage's Integer type, which generally offers much faster arithmetic operations than Python's long type:

     sage: # laptop performance
     sage: x = randrange(2**1000000)
     sage: y = randrange(2**500000)
     sage: time r = x % y
     Time: CPU 9.15 s, Wall: 9.21 s
     sage: time s = x * y
     Time: CPU 1.06 s, Wall: 1.06 s
     sage: x2 = Integer(x)
     sage: y2 = Integer(y)
     sage: time r2 = x2 % y2
     Time: CPU 0.05 s, Wall: 0.05 s
     sage: time s2 = x2 * y2
     Time: CPU 0.02 s, Wall: 0.02 s
     sage: r2 == r
     True
     sage: s2 == s
     True

Changes in syntax between Sage and Python

If you use Python then you won't have any serious trouble reading or writing Sage code, but there are a few important syntactic differences to keep in mind:

^ is exponentiation in Sage but xor in Python. For example, 2^3 is 8 in Sage and 1 in Python.
/ is exact division in Sage (producing an integer or rational) and in Python 3 (producing a floating-point number), but it is truncated division in Python 2. Python 2, Python 3, and Sage all support // for truncated division.

Using Sage

There are three different ways that you can try Sage:

Download and compile the Sage source:

     aptitude install \
       build-essential m4 gfortran imagemagick texlive dvipng libssl-dev dpkg-dev
     wget http://mirrors.xmission.com/sage/src/sage-5.5.tar
     tar -xf sage-5.5.tar
     cd sage-5.5
     env MAKE="make -j4" make

This takes a while so you should start now (and make sure your laptop has long-term power).

Download the Sage binaries.
Use one of the online Sage notebooks.

Command-line usage example:

     $ sage
     ----------------------------------------------------------------------
     | Sage Version 5.5, Release Date: 2012-12-22                         |
     | Type "notebook()" for the browser-based notebook interface.        |
     | Type "help()" for help.                                            |
     ----------------------------------------------------------------------
     sage: 2+2
     4
     sage:

Version: This is version 2012.12.27 of the sage.html web page.