home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 9 / 09.iso / e / e007 / 3.img / FILES / EXAMPLES.PAK / ONELINER.M < prev    next >
Encoding:
Text File  |  1992-07-29  |  6.3 KB  |  177 lines
  1.  
  2. (*:Version: Mathematica 2.0 *)
  3.  
  4. (*:Name: Examples`OneLiners` *)
  5.  
  6. (*:Title: Examples of efficient one line programs *)
  7.  
  8. (*:Author: Ilan Vardi
  9.  
  10. *)
  11.  
  12. (*:Keywords: Efficiency, elegance *)
  13.  
  14. (*:Requirements: none. *)
  15.  
  16. (*:Warnings: none *)
  17.  
  18. (* Source: Ilan Vardi, "Computational Recreations in Mathematica,"
  19.            Addison Wesley 1991.
  20.  
  21.            Paul Abbott, "Mathematica One-Liners", Mathematica Journal, 
  22.            Fall 1990, pages 38-41.
  23. *)
  24.  
  25. (*:Limitations:  SquareFreeQ[] can be made more efficient by checking
  26.                  for divisibility by small square factors.
  27.  
  28.                 The entries of the circulant matrix m in 
  29.                 DetCirculant[m] are assumed to have floating point
  30.                 entries.
  31.  
  32.                 SumOfSquaresR2[n] only needs the factorization of n,
  33.                 not the divisors of n, so can be made to run faster
  34.                 on numbers with many prime factors (for example 200!)
  35.                 by using FactorInteger directly.
  36.  
  37.                 Note that Subsets[x] requires that x is also a set, in
  38.                 other words that x has no repeated elements. 
  39. *)
  40.  
  41. (*:Discussion:  The programs below are designed with efficiency and
  42.                 elegance in mind and so do not just represent Mathematica
  43.                 "hacks". In general, the programs will run in about the 
  44.                 same order of efficiency as the fastest programs. Most of
  45.                 these programs are discussed in "Computational Recreations
  46.                 in Mathematica," abbreviated as CRM here.
  47.  
  48.                 It is conjectured that in general, SquareFreeQ needs 
  49.                 FactorInteger as a subroutine. Though this program can
  50.                 be made more efficient by checking for small square 
  51.                 divisors, in some sense this version is close to optimal.
  52.  
  53.                 DigitsToNumber uses Horner's rule to get a number
  54.                 back from its digital representation in a given base.
  55.                 See CRM, Chapter 3.
  56.  
  57.                 DetCirculant uses the well-known formula for determinants
  58.                 of circulants. See CRM, Chapter 6.
  59.  
  60.                 gcd[a, b] is a good example of recursion.
  61.  
  62.                 The Subsets program is interesting since it does not
  63.                 use recursion or iteration. The ideas involved are 
  64.                 discussed in CRM, Chapter 1. The program was originally
  65.                 written by Ilan Vardi and made more efficient and 
  66.                 elegant by Stan Wagon.
  67.  
  68.                 Gray was originally written by Igor Rivin and Stephen Wolfram,
  69.                 and then improved slightly by Ilan Vardi. 
  70.  
  71.                 SumOfSquaresR2[n] implements a well known formula for
  72.                 the number of representation of a number as a sum of
  73.                 two squares, where the power I^k is used to code Mod[k, 4].
  74.                 For a proof see R. Crandall, "Mathematica for the Sciences,"
  75.                 Addison Wesley 1991, page 46.
  76.  
  77.                 This FromCycles appears as Exercise 0.2 in the Preface
  78.                 of CRM.  The idea is to use the fact that if you rotate
  79.                 each cycle in this representation once, then each number 
  80.                 sits above its image in the permutation.
  81.  
  82.                 This implementation of SwinnertonDyerP[] seems to be 
  83.                 optimally efficient as well as very concise. See 
  84.                 Exercise 1.2 of CRM.
  85.  
  86.                 IntegerSpiral represents an elegant way to use the
  87.                 Gaussian integers to generate a spiral on the integer
  88.                 lattice in the plane. It is an improved version of 
  89.                 the program given in Paul Abbott's article above.
  90.                 This implementation gives a spiral of length 
  91.                 (n/2)^2 + 1 - Mod[n, 2]/4, which differs from the 
  92.                 length computed in the above article.
  93. *)
  94.  
  95. BeginPackage["Examples`OneLiners`"]
  96.  
  97. SquareFreeQ::usage = "SquareFreeQ[n] returns True if n is not divisible
  98. by the square of a prime, and False otherwise."
  99.  
  100. DigitsToNumber::usage = "DigitsToNumber[list, b] returns the
  101. integer whose base b digits are given by list."
  102.  
  103. DetCirculant::usage = "DetCirculant[m] computes the determinant of the
  104. circulant matrix m, i.e., m is a matrix whose rows are cyclic shifts
  105. of the first row. The entries are assumed to be floating-point
  106. numbers."
  107.  
  108. gcd::usage = "gcd[a, b] is a top-level implementation using the
  109. Euclidean algorithm of the built-in GCD with two arguments."
  110.  
  111. Subsets::usage = "Subsets[x] generates the subsets of the set x."
  112.  
  113. Gray::usage = "Gray[n] generates the reflected Gray code ordering of the 
  114. integers 1,...,2^n where two integers are considered adjacent if they 
  115. differ by a power of 2."
  116.  
  117. FromCycles::usage = "FromCycles[x] returns the permutation whose cycle
  118. structure is given by x."
  119.  
  120. SumOfSquaresR2::usage = "SumOfSquaresR2[n] gives the number of
  121. representations of the positive integer n as a sum of two squares
  122. where order and sign matters."
  123.  
  124. SwinnertonDyerP::usage = "SwinnertonDyerP[n, x] computes the minimal 
  125. polynomial of the sqrt's of the first n primes."
  126.  
  127. IntegerSpiral::usage = "IntegerSpiral[n] gives the {x,y} coordinates
  128. of a spiral of length ((n/2)^2 + 1 - Mod[n, 2]/4) on the integer
  129. lattice in the plane."
  130.  
  131. Begin["`Private`"]  
  132.  
  133.  
  134. SquareFreeQ[n_]:= MoebiusMu[n] != 0
  135.  
  136.  
  137. DigitsToNumber[list_, b_]:= Fold[#1 b + #2&, 0, list]
  138.  
  139.  
  140. gcd[a_, b_]:= If[b == 0, a, gcd[b, Mod[a, b]]]
  141.  
  142.  
  143. DetCirculant[m_]:= Re[Times @@ Fourier[Sqrt[N[Length[m]]] First[m]]]
  144.  
  145.  
  146. Subsets[x_]:= Flatten /@ Distribute[{{}, {#}}& /@ x, List]
  147.  
  148.  
  149. Gray[n_]:= Nest[Join[#, Length[#] + Reverse[#]]&, {1}, n]
  150.  
  151.  
  152. FromCycles[cyc_]:= 
  153. Last /@ Sort[Transpose[Flatten /@ {RotateRight /@ cyc, cyc}]]
  154.  
  155.  
  156. SumOfSquaresR2[n_]:= If[EvenQ[n], SumOfSquaresR2[n/2], 
  157.                         If[I^n == -I, 0, 4 Plus @@ Im[I^Divisors[n]]]]
  158.  
  159. SwinnertonDyerP[n_, x_]:= 
  160. Fold[Expand[(#1 /. x-> x + #2) (#1 /. x-> x - #2)]&,
  161.      x, Sqrt[Prime[Range[n]]]]
  162.  
  163.  
  164. IntegerSpiral[n_]:= 
  165.    {Re[#], Im[#]}& /@ 
  166.    Fold[Join[#1, Last[#1] + I^#2 Range[#2/2]]&, {0}, Range[n]]
  167.  
  168.  
  169. End[]   (* Examples`OneLiners`Private` *)
  170.  
  171. Protect[SquareFreeQ, DigitsToNumber, gcd, DetCirculant, Gray, 
  172.         SumOfSquaresR2, Subsets, FromCycles, SwinnertonDyerP, 
  173.         IntegerSpiral]
  174.  
  175. EndPackage[]   (* Examples`OneLiners` *)
  176.  
  177.