Changeset 6006
 Timestamp:
 Mar 9, 2007, 5:20:36 AM (13 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/ccl/level0/l0numbers.lisp
r5691 r6006 1717 1717 (low (ldb (byte 16 0) ticks))) 1718 1718 (declare (fixnum high low)) 1719 (values (the fixnum (ash high ( 16 target::fixnumshift))) 1720 (the fixnum (ash low ( 16 target::fixnumshift)))))) 1719 (values high low))) 1721 1720 1722 1721 … … 1737 1736 (t (reportbadarg number '(or (integer (0)) (float (0.0))))))) 1738 1737 1739 (defun %bignumrandom (number &optional state) 1738 1739 # 1740 Date: Mon, 3 Feb 1997 10:04:08 0500 1741 To: infomcl@digitool.com, wineberg@franz.scs.carleton.ca 1742 From: dds@flavors.com (Duncan Smith) 1743 Subject: Re: More info on the random number generator 1744 Sender: ownerinfomcl@digitool.com 1745 Precedence: bulk 1746 1747 The generator is a Linear Congruential Generator: 1748 1749 X[n+1] = (aX[n] + c) mod m 1750 1751 where: a = 16807 (Park&Miller recommend 48271) 1752 c = 0 1753 m = 2^31  1 1754 1755 See: Knuth, Seminumerical Algorithms (Volume 2), Chapter 3. 1756 1757 The period is: 2^31  2 (zero is excluded). 1758 1759 What makes this generator so simple is that multiplication and addition mod 1760 2^n1 is easy. See Knuth Ch. 4.3.2 (2nd Ed. p 272). 1761 1762 ab mod m = ... 1763 1764 If m = 2^n1 1765 u = ab mod 2^n 1766 v = floor( ab / 2^n ) 1767 1768 ab mod m = u + v : u+v < 2^n 1769 ab mod m = ((u + v) mod 2^n) + 1 : u+v >= 2^n 1770 1771 What we do is use 2b and 2n so we can do arithemetic mod 2^32 instead of 1772 2^31. This reduces the whole generator to 5 instructions on the 680x0 or 1773 80x86, and 8 on the 60x. 1774 1775 Duncan 1776 1777 # 1778 1779 #+64bittarget 1780 (defun %nextrandompair (high low) 1781 (let* ((n (nthvalue 1782 1 1783 (%multiply 42871 (dpb (ldb (byte 15 0) high) 1784 (byte 16 16) 1785 (ldb (byte 16 0) low )))))) 1786 (values (ldb (byte 16 16) n) 1787 (ldb (byte 16 0) n)))) 1788 1789 (defun %nextrandomseed (state) 1790 (multiplevaluebind (high low) (%nextrandompair (%svref state 1) 1791 (%svref state 2)) 1792 (setf (%svref state 1) (ldb (byte 15 0) high) 1793 (%svref state 2) low) 1794 high 1795 )) 1796 1797 1798 (defun %bignumrandom (number state) 1740 1799 (let* ((bits (+ (integerlength number) 8)) 1741 1800 (halfwords (ash (the fixnum (+ bits 15)) 4))
Note: See TracChangeset
for help on using the changeset viewer.