(*:Version: Mathematica 2.0 *)
(*:Name: Miscellaneous`OneLiners` *)
(*:Title: Examples of efficient one line programs *)
(*:Author: Ilan Vardi
*)
(*:Keywords: Efficiency, elegance *)
(*:Requirements: none. *)
(*:Warnings: none. *)
(* Source: Ilan Vardi, "Computational Recreations in Mathematica,"
Addison Wesley 1991
Paul Abbott, "Mathematica One-Liners" Mathematica Journal,
Fall 1990, pages 38-41
*)
(*:Limitations: SquareFreeQ[] can be made more efficient by checking
for divisibility by small square factors.
The entries of the circulant matrix in
DetCirculant[] are assumed to have floating point
entries.
r2[n] only relies on the factorization of n, not
the divisors of n, so can be made to run faster
on numbers with many prime factors (for example 200!).
This implementation of Subsets can be made more efficient
by using one of the more usual programming paradigms.
Note that Subsets[x] requires that x is also a set, in
other words that x have no repeated elements.
*)
(*:Discussion: The programs below are designed with efficiency and
elegance in mind and so do not just represent Mathematica
"hacks". In general, the programs will run in about the
same order of efficiency as the fastest programs. Most of
these programs are discussed in "Computational Recreations
in Mathematica," abbreviated as CRM here.
It is conjectured that in general, SquareFreeQ needs
FactorInteger as a subroutine. Though this program can
be made more efficient by checking for small square
divisors, in some sense this version is close to optimal.
DigitsToNumber uses Horner's rule to get a number
back from its digital representation in a given base.
See CRM, Chapter 3.
DetCirculant uses the well-known formula for determinants
of circulants. See CRM, Chapter 6.
gcd[a, b] is a good example of recursion.
Gray was originally written by Igor Rivin and Stephen Wolfram,
and then improved slightly by Ilan Vardi.
r2[n] implements a well known formula for the number
of representation of a number as a sum of two squares,
where the power I^k is used to code Mod[k, 4].
For a proof see R. Crandall, "Mathematica for the Sciences,"
Addison Wesley 1991, page 46.
This Subsets program is discussed in CRM, Chapter 1.
This FromCycles appears as Exercise 0.2 in the Preface
of CRM. The idea is to use the fact that if you rotate
each cycle in this representation once, then each number
sits above its image in the permutation.
This implementation of SwinnertonDyerP[] seems to be
optimally efficient as well as very concise. See
Exercise 1.2 of CRM.
IntegerSpiral represents an elegant way to use the
Gaussian integers to generate a spiral on the integer
lattice in the plane. It is an improved version of
the program given in Paul Abbott's article above.
*)
BeginPackage["Miscellaneous`OneLiners`"]
SquareFreeQ::usage = "SquareFreeQ[n] returns True if n is not divisible
by the square of a prime, and False otherwise."
DigitsToNumber::usage = "DigitsToNumber[list, b] returns the
integer whose base b digits are given by list."
DetCirculant::usage = "Computes the determinant of a circulant matrix, i.e.,
a matrix whose rows are cyclic shifts of the first row. The entries are
assumed to be floating-point numbers."
gcd::usage = "gcd[a, b] is a top-level implementation using the
Euclidean algorithm of the built-in GCD with two arguments."
Gray::usage = "Gray generates the reflected Gray code ordering of the
integers 1,...,2^n where two integers are considered adjacent if they
differ by a power of 2."
Subsets::usage = "Subsets generates the subsets of a set."
FromCycles::usage = "Takes a list of cycles of a permutation and
returns the permutation."
r2::usage = "Gives the number of representations of a positive integer as a
sum of two squares where order and sign matters."
SwinnertonDyerP::usage = "SwinnertonDyerP[n, x] computes the minimal
polynomial of the sqrt's of the first n primes."
IntegerSpiral::usage = "Gives the {x,y} coordinates of a spiral on the
integer lattice in the plane."
Begin["`Private`"]
SquareFreeQ[n_]:= MoebiusMu[n] != 0
DigitsToNumber[list_, b_]:= Fold[#1 b + #2&, 0, list]
gcd[a_, b_]:= If[b == 0, a, gcd[b, Mod[a, b]]]
DetCirculant[matrix_]:= Re[Times @@ Fourier[First[matrix]]]
Gray[n_]:= Nest[Join[#, Length[#] + Reverse[#]]&, {1}, n]
Subsets[x_]:= Distribute[{{}, {#}}& /@ x, List, List, List, Union]
FromCycles[cyc_]:=
Last /@ Sort[Transpose[Flatten /@ {RotateRight /@ cyc, cyc}]]
r2[n_]:= If[EvenQ[n], r2[n/2],
If[I^n == -I, 0, 4 Plus @@ Im[I^Divisors[n]]]]
SwinnertonDyerP[n_, x_]:=
Fold[Expand[(#1 /. x-> x + #2) (#1 /. x-> x - #2)]&,
x, Sqrt[Prime[Range[n]]]]
IntegerSpiral[n_]:=
{Re[#], Im[#]}& /@
Fold[Join[#1, Last[#1] + I^#2 Range[#2/2]]&, {0}, Range[n]]
End[] (* Miscellaneous`OneLiners`Private` *)
Protect[SquareFreeQ, DigitsToNumber, gcd, DetCirculant, Gray, r2,
Subsets, FromCycles, SwinnertonDyerP, IntegerSpiral]
EndPackage[] (* Miscellaneous`OneLiners` *)