From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,6fb545e0f992d3a9 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-08-15 22:17:14 PST Path: archiver1.google.com!newsfeed.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!howland.erols.net!news-out.worldnet.att.net.MISMATCH!wn3feed!worldnet.att.net!135.173.83.71!wnfilter1!worldnet-localpost!bgtnsc04-news.ops.worldnet.att.net.POSTED!not-for-mail From: "David Thompson" Newsgroups: comp.lang.ada References: <3B71AC13.F67BDC2@cadence.com> Subject: Re: Wraparound on multiply overflow X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.00.2615.200 X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2615.200 Message-ID: Date: Thu, 16 Aug 2001 05:17:13 GMT NNTP-Posting-Host: 12.89.147.208 X-Complaints-To: abuse@worldnet.att.net X-Trace: bgtnsc04-news.ops.worldnet.att.net 997939033 12.89.147.208 (Thu, 16 Aug 2001 05:17:13 GMT) NNTP-Posting-Date: Thu, 16 Aug 2001 05:17:13 GMT Organization: AT&T Worldnet Xref: archiver1.google.com comp.lang.ada:11970 Date: 2001-08-16T05:17:13+00:00 List-Id: Paul Graham wrote : > In C it is defined that the result of multiplying two unsigned integers > is the mathematical result modulo the value (int_max + 1), where int_max > is the maximum unsigned integer. More precisely, the result of any arithmetic operation in, or conversion from a wider integer type to, an unsigned (integer) type is taken modulo the maximum value _of that type_ plus 1, which must be a power of two (because unsigned integer types, and the magnitude portions of signed integer types, are required to be in "pure binary"). For unsigned int in particular, this is UINT_MAX in . INT_MAX (uppercase; C is case-sensitive) is the maximum value of _signed_ int. > ... I'm interested in porting to Ada a > random number generator which relies on this rule. The code looks like: > > unsigned int X[10]; > ... > X[0] = seed; > for (i = 1; i <= 10; i++) > X[i] = X[i-1] * 12345; > This code stores to X[10] which does not exist. An array of size N in C has elements 0 .. N-1. > The idea is that a table of random looking numbers is created by > repeated multiplication of a seed by some constant. This sequence is > guaranteed to be the same across conforming C implementations, because > of the modulo rule I mentioned above. > It's guaranteed to be well-defined: not to produce a trap or signal or garbage result or error message or any of the many other possible faces of Undefined Behavior, which does occur for _signed_ integer overflow in C. But it is _not_ guaranteed to be the _same_, because the number of (value) bits in unsigned int (or any other integer type except as a bit-field member of a struct) is not standardized, only (indirectly) a _minimum_ (16 for unsigned int), and using a different power-of-two modulus gives a different sequence. I hope (from your wording) this is just a learning exercise. Know, if you don't already, that the numbers produced by a Linear Congruential Generator (LCG) such as this may "look random" to an unaided and untrained human, but mathematically are easily distinguished from random. No software/algorithm-generated numbers are truly random (cf John von Neumann), but for many statistical and/or security/cryptographic applications, there are much better pseudo-random generators -- but not on topic here, except(?) those provided by Ada implementations under A.5.2 (and G.2.5). -- - David.Thompson 1 now at worldnet.att.net