BBC BASIC's RND Function

Hi all, I have been attempting to use BASIC's RND function to generate a 
number between 0 and 14

in a weird attempt to use the stronghelp manual, I tried to use

Highest% = 14
tmp_int% = RND(Highest%)

but the manual says it generates a number between 1 and INT(n) (Highest% 
in this case)

in VisualBASIC I can remember generating a number between any to any 
(integer wise) using something like:

int_temp = RND(int_Lowest,int_Highest)

so int_Lowest could have been -50 ect


how would I do this in BBC BASIC as I cannot find any reference to this 
kind of function

Cheers
0
Michael
10/12/2007 10:41:15 AM
comp.sys.acorn.programmer 2446 articles. 0 followers. Post Follow

58 Replies
397 Views

Similar Articles

[PageSpeed] 14
In article <fbIPi.75705$yN2.50091@newsfe7-gui.ntli.net>,
   Michael Emerton <MichaelREmerton@_deleteme_hotmail.com> wrote:

> how would I do this in BBC BASIC as I cannot find any reference to this 
> kind of function

Subtract a constant?

Eg,

        Highest% = 14
        tmp_int% = RND(Highest%)-2

will generate a number between -1 and 12.

Best not to capitalise your variables.

John

-- 
John Williams, Brittany, Northern France - no attachments to these addresses!
Non-RISC OS posters change user to johnrwilliams or put 'risc' in subject
for reliable contact! Who is John Williams? http://www.picindex.info/author/ 
Somewhere nice to stay in Brittany? http://petit.four.free.fr/visitors/locate
0
UCEbin (2770)
10/12/2007 10:46:21 AM
> Subtract a constant?
> 
> Eg,
> 
>         Highest% = 14
>         tmp_int% = RND(Highest%)-2
> 
> will generate a number between -1 and 12.

Hmm didn't think of that! :) thanks!

> 
> Best not to capitalise your variables.

Damn! better change my progs now then ;@)
0
Michael
10/12/2007 10:59:49 AM
In article <fbIPi.75705$yN2.50091@newsfe7-gui.ntli.net>,
   Michael Emerton <MichaelREmerton@_deleteme_hotmail.com> wrote:

> Hi all, I have been attempting to use BASIC's RND function to
> generate a number between 0 and 14

> in a weird attempt to use the stronghelp manual, I tried to use

> Highest% = 14
> tmp_int% = RND(Highest%)

> but the manual says it generates a number between 1 and INT(n)
> (Highest% in this case)

> in VisualBASIC I can remember generating a number between any to
> any (integer wise) using something like:

> int_temp = RND(int_Lowest,int_Highest)

BASICs vary. RND doubly so. :p

To get a random number between 0 and n in BBC BASIC, use RND(n+1)-1

The RND(n+1) gives you a random number between 1 and 1 /more/ than
your upper limit, and the -1 then deducts 1 from that number - so the
result is between 0 and n.

> so int_Lowest could have been -50 ect

> how would I do this in BBC BASIC as I cannot find any reference to
> this kind of function

An equivalent to the VB function you describe[1] would be:

DEF FN_VBRND(lowest%,highest%)=RND(highest%-lowest%+1)+lowest%-1

[1] Which doesn't seem to be what I remember it being in VB, but
never mind. :)

-- 
http://www.softrock.co.uk
http://www.riscository.com
http://www.webchange.co.uk
http://www.vinceh.com
0
spam5752 (1717)
10/12/2007 11:09:23 AM
>> in VisualBASIC I can remember generating a number between any to
>> any (integer wise) using something like:
> 
>> int_temp = RND(int_Lowest,int_Highest)
>
> An equivalent to the VB function you describe[1] would be:
> 
> DEF FN_VBRND(lowest%,highest%)=RND(highest%-lowest%+1)+lowest%-1
> 
> [1] Which doesn't seem to be what I remember it being in VB, but
> never mind. :)

My memory must be failing :P was over 7 years ago since I last used a 
random generator!

0
Michael
10/12/2007 11:41:18 AM
In article <y3JPi.15665$DB2.7179@newsfe1-win.ntli.net>,
   Michael Emerton <MichaelREmerton@_deleteme_hotmail.com> wrote:
> My memory must be failing :P was over 7 years ago since I last used a 
> random generator!

Also note that putting a -ve number into RND will initialise the
pseudo-random number sequence. So if you need a repeatable pattern of
randomish behaviour, doing:

  IF RND(-1)

would start the sequence at -1.

If you want a much _more_ random number generator, take a look at the
CryptRandom module at:

  http://www.chiark.greenend.org.uk/~theom/riscos/crypto/

I think you can then simply do:

  SYS "CryptRandom_Word" TO rnd%

to give you a random value (but not in a specific range). To get it into a
specific range (from 0 to n-1) you'd add something like:

  word% = ABS(word% MOD range%)

Steve

-- 
Steve Revill @ Home
Note: All opinions expressed herein are my own.
0
steve417 (852)
10/12/2007 12:45:14 PM
Michael Emerton wrote:
> Hi all, I have been attempting to use BASIC's RND function to generate a 
> number between 0 and 14
> 
> in a weird attempt to use the stronghelp manual, I tried to use
> 
> Highest% = 14
> tmp_int% = RND(Highest%)
> 
> but the manual says it generates a number between 1 and INT(n) (Highest% 
> in this case)
> 
> in VisualBASIC I can remember generating a number between any to any 
> (integer wise) using something like:
> 
> int_temp = RND(int_Lowest,int_Highest)
> 
> so int_Lowest could have been -50 ect> 
> 
> how would I do this in BBC BASIC as I cannot find any reference to this 
> kind of function

Try:

 int_temp = FNrnd(int_Lowest,int_Highest)
 END
 
 DEF FNrnd(L%,H%) = L%+RND(H%-L%+1)-1

-- 
 ;  ,', * Basalt * - gives RO 3.10+ versions of BASIC V new and alternative
 ;,'    keywords, dynamic memory for arrays and blocks, new variable types.
 ;',    Legal, fast and simple to use. Freeware - version 0.98� - 19 Aug 03
,;  ',, Steve Drain, Kappa : http://www.kappa.me.uk/basalt.htm

0
steve3677 (307)
10/12/2007 12:49:18 PM
In article <4f309fbd4bsteve@revi11.plus.com>,
   Ste (news) <steve@revi11.plus.com> wrote:
>   SYS "CryptRandom_Word" TO rnd%
                              ^^^^
                              word%  of course
>   word% = ABS(word% MOD range%)

Steve

-- 
Steve Revill @ Home
Note: All opinions expressed herein are my own.
0
steve417 (852)
10/12/2007 1:45:15 PM
Ste (news) wrote:
> In article <4f309fbd4bsteve@revi11.plus.com>,
>    Ste (news) <steve@revi11.plus.com> wrote:
>>   SYS "CryptRandom_Word" TO rnd%
>                               ^^^^
>                               word%  of course
>>   word% = ABS(word% MOD range%)
> 
> Steve
> 


cool!

cheers to all that helped, I will try them out one by one :@)

Michael
0
Michael
10/12/2007 1:49:47 PM
On Oct 12, 1:45 pm, "Ste (news)" <st...@revi11.plus.com> wrote:
> If you want a much _more_ random number generator, take a look at the
> CryptRandom module at:
>
>  http://www.chiark.greenend.org.uk/~theom/riscos/crypto/

Somewhat OT: it's often not appreciated just how poor BASIC's RND() is
for some tasks.  A classic example is shuffling a pack of cards.
There are 52! possible arrangements of cards in a standard pack
(excluding jokers); that's about 8 * 10^67.  The total number of
possible different sequences returned from RND() is 2^33, or about 8 *
10^9.  So only about 1 in 10^58 of all the possible arrangements of
cards in a pack will *ever* be generated by a given shuffling routine
based solely on BASIC's RND, however involved it is.  Quite a
staggering statistic, if you haven't met it before.

Richard.
http://www.rtrussell.co.uk/
To reply by email change 'news' to my forename.

0
news1075 (671)
10/12/2007 3:54:45 PM
On Fri, 12 Oct 2007 08:54:45 -0700, Richard Russell wrote:

> Somewhat OT: it's often not appreciated just how poor BASIC's RND() is
> for some tasks.  A classic example is shuffling a pack of cards. There
> are 52! possible arrangements of cards in a standard pack (excluding
> jokers); that's about 8 * 10^67.  The total number of possible different
> sequences returned from RND() is 2^33, or about 8 * 10^9.  So only about
> 1 in 10^58 of all the possible arrangements of cards in a pack will
> *ever* be generated by a given shuffling routine based solely on BASIC's
> RND, however involved it is.  Quite a staggering statistic, if you
> haven't met it before.

What do you mean by "total number of possible different sequences 
returned from RND() is 2^33" ?  Is that for a given seed?  For a given 
range?  I'd assume, that given it returns a 32 bit integer, there are 
2^32 different values it can return, and assuming it's not a completely 
dire algorithm, most combinations of those 2^32 numbers should be 
possible to be generated.

Your assertion here feels like it's missing something, but I can't quite 
place what.

B.
0
nntp550 (4244)
10/12/2007 4:45:42 PM
In article <470fa4b5$0$8429$db0fefd9@news.zen.co.uk>,
   Rob Kendrick <nntp@rjek.com> wrote:
> On Fri, 12 Oct 2007 08:54:45 -0700, Richard Russell wrote:
>
> > Somewhat OT: it's often not appreciated just how poor BASIC's RND() is
> > for some tasks.  A classic example is shuffling a pack of cards. There
> > are 52! possible arrangements of cards in a standard pack (excluding
> > jokers); that's about 8 * 10^67.  The total number of possible different
> > sequences returned from RND() is 2^33, or about 8 * 10^9.  So only about
> > 1 in 10^58 of all the possible arrangements of cards in a pack will
> > *ever* be generated by a given shuffling routine based solely on BASIC's
> > RND, however involved it is.  Quite a staggering statistic, if you
> > haven't met it before.
>
> Your assertion here feels like it's missing something, but I can't quite 
> place what.

I think the missing bit is (and this is a guess) that Richard's assertion
may well be true for generating a shuffled pack _in one pass_. If however,
the algorithm does something like:

  loop n times (and/or for n centiseconds whilst multitasking)
    swap card at position RND with card at position RND

then surley there's nothing to stop you getting at all possible orders of
cards (given enough shuffles) because BASIC's RND function is based upon a
33 bits accumulator from which we're only interested in 0..51?

I do agree that it's well worth introducing some other factor which isn't so
algorithmic, like the multitasking because that can be affected by other
stuff going on in the desktop and the user's actions.

Steve

-- 
Steve Revill @ Home
Note: All opinions expressed herein are my own.
0
steve417 (852)
10/12/2007 5:45:10 PM
In message <4f309fbd4bsteve@revi11.plus.com>
          "Ste (news)" <steve@revi11.plus.com> wrote:

> In article <y3JPi.15665$DB2.7179@newsfe1-win.ntli.net>,
>    Michael Emerton <MichaelREmerton@_deleteme_hotmail.com> wrote:
> > My memory must be failing :P was over 7 years ago since I last used a 
> > random generator!
> 
> Also note that putting a -ve number into RND will initialise the
> pseudo-random number sequence. So if you need a repeatable pattern of
> randomish behaviour

Or a neat little hashing function :)


-- 
Rik Griffin
0
10/12/2007 6:58:58 PM
On 12 Oct 2007 Richard Russell <news@rtrussell.co.uk> wrote:
> Somewhat OT: it's often not appreciated just how poor BASIC's RND() is
> for some tasks.  A classic example is shuffling a pack of cards.
> There are 52! possible arrangements of cards in a standard pack
> (excluding jokers); that's about 8 * 10^67.  The total number of
> possible different sequences returned from RND() is 2^33, or about 8 *
> 10^9.  So only about 1 in 10^58 of all the possible arrangements of
> cards in a pack will *ever* be generated by a given shuffling routine
> based solely on BASIC's RND, however involved it is.  Quite a
> staggering statistic, if you haven't met it before.

No, the psuedo random number generator returns sequence of 32bit 
numbers, the full sequence repeat length is 2^33 values. All 32bit 
values occur in this sequence, but not necessarily with precisely 
equal frequency.

It is possible to generate all possible combinations of 52 cards with 
this generator, unless your algorithm is broken. The most common 
mystake in using BASIC's RND is not to seed it before starting, which 
will tend to result in exactly the same sequence every time.

The common way to seed is to use RND(-TIME), but you should bear in 
mind that TIME is reset at reboot, so will not be sufficent if used in 
a turn key system. Ideal a seed value based on part of the 5 byte real 
time clock should be used.

---druck

-- 
The ARM Club Free Software - http://www.armclub.org.uk/free/
The 32bit Conversions Page - http://www.quantumsoft.co.uk/druck/
0
news5843 (7460)
10/12/2007 7:14:47 PM
On Oct 12, 5:45 pm, Rob Kendrick <n...@rjek.com> wrote:
> What do you mean by "total number of possible different sequences
> returned from RND() is 2^33" ?  Is that for a given seed?  For a given
> range?

For a "given seed" there is only one sequence (of a certain length)
that it can generate!  Since there are only 2^31 possible seeds a
'seeded' generator can produce only that number of different
sequences.  An 'unseeded' generator can produce only a maximum of 2^33
different sequences.

> I'd assume, that given it returns a 32 bit integer, there are
> 2^32 different values it can return, and assuming it's not a completely
> dire algorithm, most combinations of those 2^32 numbers should be
> possible to be generated.

By your definition then, it's a "dire algorithm".

> Your assertion here feels like it's missing something, but I can't quite
> place what.

The very reason I mentioned it is because it is so surprising and
counter-intuitive, but it is nevertheless correct.

Richard.
http://www.rtrussell.co.uk/
To reply by email change 'news' to my forename.

0
news1075 (671)
10/12/2007 10:01:53 PM
On Fri, 12 Oct 2007 20:14:47 +0100, druck wrote:

> Ideal a seed value based on part of the 5 byte real time
> clock should be used.

Preferably with some of the least significant 16 bits of this being in 
there - I've seen code that uses the first (MS) 16 bits of the monotonic 
timer, and it doesn't have the unpredictability the author would have 
wanted.

B.
0
nntp550 (4244)
10/12/2007 10:07:03 PM
On Oct 12, 6:45 pm, "Ste (news)" <st...@revi11.plus.com> wrote:
> I think the missing bit is (and this is a guess) that Richard's assertion
> may well be true for generating a shuffled pack _in one pass_. If however,
> the algorithm does something like:
>
>   loop n times (and/or for n centiseconds whilst multitasking)
>     swap card at position RND with card at position RND
>
> then surley there's nothing to stop you getting at all possible orders of
> cards (given enough shuffles) because BASIC's RND function is based upon a
> 33 bits accumulator from which we're only interested in 0..51?

There is nothing you can do, short of introducing a different source
of 'randomness', to increase the number of possible sequences above
2^33.

Think about it.  Any algorithm you may devise, however convoluted,
which uses RND() as its sole source of 'randomness' must produce the
same sequence given the same starting conditions - it's not magic!
Since there are only 2^33 different starting conditions, there can
only be 2^33 different sequences.

> I do agree that it's well worth introducing some other factor which isn't so
> algorithmic, like the multitasking because that can be affected by other
> stuff going on in the desktop and the user's actions.

If you can introduce an additional source of 'randomness' then you can
exceed the 2^33 limit, but how do you propose to use 'multitasking' to
achieve that in a quantifiable way?

Richard.
http://www.rtrussell.co.uk/
To reply by email change 'news' to my forename.

0
news1075 (671)
10/12/2007 10:10:37 PM
On Oct 12, 8:14 pm, druck <n...@druck.freeuk.com> wrote:
> It is possible to generate all possible combinations of 52 cards with
> this generator, unless your algorithm is broken.

Rubbish.  See my other replies for the explanation.

Richard.
http://www.rtrussell.co.uk/
To reply by email change 'news' to my forename.

0
news1075 (671)
10/12/2007 10:11:19 PM
In message <3d67c3304f.druck@druck.freeuk.net>
          druck <news@druck.freeuk.com> wrote:

> On 12 Oct 2007 Richard Russell <news@rtrussell.co.uk> wrote:
>> Somewhat OT: it's often not appreciated just how poor BASIC's RND() is
>> for some tasks.  A classic example is shuffling a pack of cards.
>> There are 52! possible arrangements of cards in a standard pack
>> (excluding jokers); that's about 8 * 10^67.  The total number of
>> possible different sequences returned from RND() is 2^33, or about 8 *
>> 10^9.  So only about 1 in 10^58 of all the possible arrangements of
>> cards in a pack will *ever* be generated by a given shuffling routine
>> based solely on BASIC's RND, however involved it is.  Quite a
>> staggering statistic, if you haven't met it before.

> No, the psuedo random number generator returns sequence of 32bit
> numbers, the full sequence repeat length is 2^33 values. All 32bit
> values occur in this sequence, but not necessarily with precisely
> equal frequency.

> It is possible to generate all possible combinations of 52 cards with
> this generator, unless your algorithm is broken.

No, as Richard has pointed out, this is not possible. It follows from 
the vast number of permutations that exist, the limited cycle length 
of the generator and the fact that computers are deterministic.

> It is possible to generate all possible combinations of 52 cards with
> this generator, unless your algorithm is broken. The most common
> mystake in using BASIC's RND is not to seed it before starting, which
> will tend to result in exactly the same sequence every time.

There, you have given the solution yourself. If you have the same 
starting seed, you get the same arrangement of cards at the end. 
Agreed? Now, you only need to consider how many different starting 
seeds we have. Due to technical reasons even less than 2^33, but even 
if we could seed the generator with each of its possible 2^33 states, 
then we could only ever generate 2^33 different results from the 
program (and in practice even fewer because not all of the results 
need to be different) - and that is dramatically less than the 52! 
possible permutations of the cards.

This is not really surprising - after all, there is no randomness in a 
computer and the only source of "randomness" you have in the whole 
affair is the choice of the original seed. Things get even worse when 
you consider how that original seed is usually chosen. System time 
(TIME in BASIC) is popular. That only covers a tiny part of the entire 
2^32 range in the majority of cases because most desktop computers are 
only switched on during the day. You need to have the machine switched 
on for 11930 hours to use the full range of TIME.

Martin
-- 
---------------------------------------------------------------------
Martin Wuerthner         MW Software      http://www.mw-software.com/
   ArtWorks 2 -- Designing stunning graphics has never been easier
spamtrap@mw-software.com      [replace "spamtrap" by "info" to reply]
0
spamtrap3075 (2307)
10/12/2007 10:24:35 PM
In article <1192227037.473264.13560@z24g2000prh.googlegroups.com>,
   Richard Russell <news@rtrussell.co.uk> wrote:
> If you can introduce an additional source of 'randomness' then you can
> exceed the 2^33 limit, but how do you propose to use 'multitasking' to
> achieve that in a quantifiable way?

Use some function of the high resolution timer to reseed the random number
generator based upon the time between entering and returning from Wimp_Poll.

Steve

-- 
Steve Revill @ Home
Note: All opinions expressed herein are my own.
0
steve417 (852)
10/14/2007 1:32:46 PM
On 14 Oct 2007 "Ste (news)" <steve@revi11.plus.com> wrote:
> In article <1192227037.473264.13560@z24g2000prh.googlegroups.com>,
>    Richard Russell <news@rtrussell.co.uk> wrote:
>> If you can introduce an additional source of 'randomness' then you can
>> exceed the 2^33 limit, but how do you propose to use 'multitasking' to
>> achieve that in a quantifiable way?

> Use some function of the high resolution timer to reseed the random number
> generator based upon the time between entering and returning from Wimp_Poll.

That depends on what's running and whether the user is doing anything, 
otherwise it may not be very variable. Use my !APPstat from the fisrt 
link below to examine the wimp event timings to microsecond 
resolution.

A slightly more random seed can be generated form the time between 
user key presses. I think the CryptRandom module uses this, so that
would be a good place to look.

---druck

-- 
The ARM Club Free Software - http://www.armclub.org.uk/free/
The 32bit Conversions Page - http://www.quantumsoft.co.uk/druck/
0
news5843 (7460)
10/14/2007 6:15:32 PM
"Ste (news)" <steve@revi11.plus.com> wrote:
> In article <1192227037.473264.13560@z24g2000prh.googlegroups.com>,
>    Richard Russell <news@rtrussell.co.uk> wrote:
> > If you can introduce an additional source of 'randomness' then you can
> > exceed the 2^33 limit, but how do you propose to use 'multitasking' to
> > achieve that in a quantifiable way?
> 
> Use some function of the high resolution timer to reseed the random number
> generator based upon the time between entering and returning from Wimp_Poll.

CryptRandom attempts to hoover up as much entropy ('randomness') as it can. 
This is basically based on three sources:

Human generated:
Keypresses, mouse movements, timestamps for them

Non-transient (ie retained over reboots):
HD directory structure, HD free space, battery voltages, real time clock
Seed saved in Choices: over reboots

System environment (much weaker):
OS version, monotonic time, current dynamic areas, contents of Wimp$ScrapDir

These are repeatedly hashed together in an attempt to mix up the bits as
much as possible, and then the access SWIs read bits from the pool, hashing
as they go.  There's also an interface to the pool through accessing
/dev/urandom from UnixLib-linked programs.


What I don't currently provide is guaranteed entropy (as /dev/random does on
Unix) where the system waits until it has enough bits of entropy to fulfill
a request.  Partly because this API doesn't work on RISC OS - you'd have to
query the module for how many bits of entropy were available, and then
another process might have grabbed them before you got around to requesting
them.  Partly because it's difficult to estimate the entropy of each source
in anything other than a very conservative way (how much entropy in a
keypress? If the user is typing English, not much).  And partly because
there's usually much less happening on a RISC OS machine so fewer sources of
entropy.

Seeding the random number generator is a good way to produce longer
sequences, but remember the entropy in the system is still the 32 bit random
seed.  If you're using this to generate crypto keys, for example, that means
you only have 2^32 possible keys because you only have 2^32 seeds (and the
rest of the process is deterministic) - and a 32 bit key is trivial to
brute-force these days.  Hence the need for more entropy in the system.

Theo
0
news539 (2442)
10/14/2007 7:30:12 PM
druck <news@druck.freeuk.com> wrote:
> That depends on what's running and whether the user is doing anything, 
> otherwise it may not be very variable. Use my !APPstat from the fisrt 
> link below to examine the wimp event timings to microsecond 
> resolution.

There are three sources I can think of possible randomness there. The
biggest is user actions, but let's assume everything was run automatically
so that doesn't apply.  The others are quite small, so it's difficult to
measure them.  The first is hard disc latency, which will depend on the
initial position of the disc and turbulence (there's an interesting paper on
this here: http://world.std.com/~dtd/random/forward.ps )

The second is phase noise: taking the difference of two decoupled clocks
will produce randomised jitter between them.  This might be the case if the
DRAM runs off a different clock from the CPU, and they're not synchronised -
this would show through jitter in memory access times. But lack of
synchronisation is the bane of a designer's life (metastability issues) so
is avoided wherever possible, and power supply noise has a habit of pulling
de-synchronised clocks into line.

Linux uses disc latencies to provide randomness, which isn't something
that's feasible for third-party code on RISC OS.  Clock jitter would be
difficult to measure non-invasively, though many smartcards have a random
number generator that operates on this principle.

Theo
0
news539 (2442)
10/14/2007 9:29:52 PM
In message <yGt*rUjXr@news.chiark.greenend.org.uk>
       Theo Markettos <theom+news@chiark.greenend.org.uk> wrote:

> "Ste (news)" <steve@revi11.plus.com> wrote:
> > In article <1192227037.473264.13560@z24g2000prh.googlegroups.com>,
> >    Richard Russell <news@rtrussell.co.uk> wrote:
> > > If you can introduce an additional source of 'randomness' then
> > > you can exceed the 2^33 limit, but how do you propose to use
> > > 'multitasking' to achieve that in a quantifiable way?
> > 
> > Use some function of the high resolution timer to reseed the random
> > number generator based upon the time between entering and returning
> > from Wimp_Poll.
> 
> CryptRandom attempts to hoover up as much entropy ('randomness') as
> it can.  This is basically based on three sources:

[SNIP]

> Seeding the random number generator is a good way to produce longer
> sequences, but remember the entropy in the system is still the 32 bit
> random seed.  If you're using this to generate crypto keys, for
> example, that means you only have 2^32 possible keys because you only
> have 2^32 seeds (and the rest of the process is deterministic) - and
> a 32 bit key is trivial to brute-force these days.  Hence the need
> for more entropy in the system.

One thing that has been missed in this thread is the purpose for which
the stream is needed.

If the only requirement is a much longer cycle length than RND (while
retaining the ability to guarantee repeatability by seeding it), then
it shouldn't take much ingenuity to implement a BASIC version of the
Mersenne Twister (cycle length 2^19937 - 1), which is pretty fast[1]
for a generator of such cycle length.

  http://en.wikipedia.org/wiki/Mersenne_twister

MT has some flaws that make it inappropriate for cryptography, though.

[1] My test implementation on x86 hardware showed it is pretty much the
same as the standard C Knuth generator.

-- 
Nick Roberts           tigger @ orpheusinternet.co.uk           

Hanlon's Razor: Never attribute to malice that which
can be adequately explained by stupidity.
0
tigger2145 (262)
10/15/2007 6:14:28 PM
In message <a96349324f.tigger@bc63.orpheusinternet.co.uk>
          Nick Roberts <tigger@orpheusinternet.co.uk> wrote:

> In message <yGt*rUjXr@news.chiark.greenend.org.uk>
>        Theo Markettos <theom+news@chiark.greenend.org.uk> wrote:

>> Seeding the random number generator is a good way to produce longer
>> sequences, but remember the entropy in the system is still the 32 bit
>> random seed.  If you're using this to generate crypto keys, for
>> example, that means you only have 2^32 possible keys because you only
>> have 2^32 seeds (and the rest of the process is deterministic) - and
>> a 32 bit key is trivial to brute-force these days.  Hence the need
>> for more entropy in the system.

> One thing that has been missed in this thread is the purpose for which
> the stream is needed.

Not at all, we have been discussing the all important task of 
shuffling cards, which turned out to be surprisingly difficult. :-)

> If the only requirement is a much longer cycle length than RND (while
> retaining the ability to guarantee repeatability by seeding it), then
> it shouldn't take much ingenuity to implement a BASIC version of the
> Mersenne Twister (cycle length 2^19937 - 1), which is pretty fast[1]
> for a generator of such cycle length.

The standard implementation of MT 19937 has a 32-bit seed, so we are 
back to a maximum of 2^32 different arrangements of the cards, no 
matter how big the cycle length is. :-( In fact, the cycle length is 
not really that important for this particular application. It is 
important in that it limits the starting entropy because you cannot 
have more different seed values than the length of the cycle. Unless 
you have at least 226 bits of entropy to start with (i.e., in the 
seed) it is impossible to achieve all permutations of a pack of 52 
cards.

It should be possible to create MTs with larger word lengths but then, 
I suppose that speed will suffer.

Martin
-- 
---------------------------------------------------------------------
Martin Wuerthner         MW Software      http://www.mw-software.com/
   ArtWorks 2 -- Designing stunning graphics has never been easier
spamtrap@mw-software.com      [replace "spamtrap" by "info" to reply]
0
spamtrap3075 (2307)
10/15/2007 9:18:52 PM
On Oct 15, 7:14 pm, Nick Roberts <tig...@orpheusinternet.co.uk> wrote:
> it shouldn't take much ingenuity to implement a BASIC version of the
> Mersenne Twister (cycle length 2^19937 - 1)

I have listed below a BBC BASIC for Windows implementation of the
MT19937 algorithm, which wouldn't need much modification to run under
RISC OS (it uses a tiny amount of assembler code, and a couple of
PRIVATE variables which would have to be changed to globals).

Richard.
http://www.rtrussell.co.uk/
To reply by email change 'news' to my forename.

      REM MT19937 Mersenne Twister by Richard Russell

      seed% = FNmersenne(-ABS(TIME))
      FOR N% = 1 TO 30
        PRINT FNmersenne(52)
      NEXT
      END

      DEF FNmersenne(R%)
      PRIVATE MT%(), J%
      LOCAL I%, Y%
      DIM MT%(623)
      IF R%<0 THEN
        LOCAL A%, B%, C%, P%, Q%
        DIM P% LOCAL 20
        [OPT 2:.Q% mov edx,eax:shr eax,30:xor eax,edx:mul ebx:add
eax,ecx:ret:]
        MT%(0) = -R%
        B% = 1812433253
        FOR C% = 1 TO 623
          A% = MT%(C%-1)
          MT%(C%) = USR(Q%)
        NEXT
        J% = 624
        = R%
      ENDIF
      REPEAT
        IF J% = 624 THEN
          REM Generate an array of 624 untempered numbers:
          FOR I% = 0 TO 623
            Y% = (MT%(I%) AND &80000000) OR (MT%((I%+1) MOD 624) AND
&7FFFFFFF)
            MT%(I%) = MT%((I% + 397) MOD 624) EOR (Y% >>> 1)
            IF (Y% AND 1) MT%(I%) EOR= &9908B0DF
          NEXT
          J% = 0
        ENDIF
        REM Extract a tempered pseudorandom 32-bit number:
        Y% = MT%(J%)
        J% += 1
        Y% EOR= Y% >>> 11
        Y% EOR= (Y% << 7) AND &9D2C5680
        Y% EOR= (Y% << 15) AND &EFC60000
        Y% EOR= Y% >>> 18
        IF R%<=0 THEN = Y% : REM Return 32-bit integer
      UNTIL (Y% AND &7FFFFFFF) < ((&7FFFFFFF DIV R%) * R%)
      = (Y% AND &7FFFFFFF) MOD R% + 1 : REM Return value in range 1 to
R%

0
news1075 (671)
10/15/2007 9:25:06 PM
In message <a1455a324f.martin@bach.planiverse.com>
       Martin Wuerthner <spamtrap@mw-software.com> wrote:

> In message <a96349324f.tigger@bc63.orpheusinternet.co.uk>
>           Nick Roberts <tigger@orpheusinternet.co.uk> wrote:
> 
[snip]

> > one thing that has been missed in this thread is the purpose for
> > which the stream is needed.
> 
> Not at all, we have been discussing the all important task of 
> shuffling cards, which turned out to be surprisingly difficult. :-)

I noted the shuffling cards, but that wasn't what started the thread...

> 
> > If the only requirement is a much longer cycle length than RND
> > (while retaining the ability to guarantee repeatability by seeding
> > it), then it shouldn't take much ingenuity to implement a BASIC
> > version of the Mersenne Twister (cycle length 2^19937 - 1), which
> > is pretty fast[1] for a generator of such cycle length.
> 
> The standard implementation of MT 19937 has a 32-bit seed, so we are 
> back to a maximum of 2^32 different arrangements of the cards, no 
> matter how big the cycle length is. :-( In fact, the cycle length is 
> not really that important for this particular application. It is 
> important in that it limits the starting entropy because you cannot 
> have more different seed values than the length of the cycle. Unless 
> you have at least 226 bits of entropy to start with (i.e., in the 
> seed) it is impossible to achieve all permutations of a pack of 52 
> cards.

> It should be possible to create MTs with larger word lengths but
> then,  I suppose that speed will suffer.

There's no need to have a larger word length, surely. You should be
able to seed each of the 624 dimensions with a separate seed, giving
you a seed of 624 * 32 bits. The classic implementation of initializing
each of the 623 subsequent words with 69069 times the previous one is
simply applying a fairly crude multiplicative congruential RNG to each
word.

OK, you then need a mechanism to seed each word rather than using a
single 32-bit word, but in principle that is achievable.

An application I had at work had a need for a cycle length of approx
10^60, but unfortunately it also had to be multiplicative congruential
(it had to be possible to generate the nth number in the sequence
without generating the n-1 numbers in between, and to the best of my
knowledge only MC RNGs have this property). That was a monster...

-- 
Nick Roberts           tigger @ orpheusinternet.co.uk           

Hanlon's Razor: Never attribute to malice that which
can be adequately explained by stupidity.
0
tigger2145 (262)
10/16/2007 5:09:52 PM
On Tue, 16 Oct 2007 18:09:52 +0100, Nick Roberts wrote:

> An application I had at work had a need for a cycle length of approx
> 10^60, but unfortunately it also had to be multiplicative congruential
> (it had to be possible to generate the nth number in the sequence
> without generating the n-1 numbers in between, and to the best of my
> knowledge only MC RNGs have this property). That was a monster...

How random did it have to be?  If it doesn't have to be *that* random, a 
simple solution springs to mind: use a cryptographic hash over counter.

B.
0
nntp550 (4244)
10/17/2007 6:40:08 PM
In article <47165708$0$13932$fa0fcedb@news.zen.co.uk>,
   Rob Kendrick <nntp@rjek.com> wrote:
> On Tue, 16 Oct 2007 18:09:52 +0100, Nick Roberts wrote:
>
> > An application I had at work had a need for a cycle length of approx
> > 10^60, but unfortunately it also had to be multiplicative congruential
> > (it had to be possible to generate the nth number in the sequence
> > without generating the n-1 numbers in between, and to the best of my
> > knowledge only MC RNGs have this property). That was a monster...
>
> How random did it have to be?  If it doesn't have to be *that* random, a 
> simple solution springs to mind: use a cryptographic hash over counter.

Or use value n to seed a RNG then take the next number that pops out of that
RNG, assuming that will be the same each time for a given n. Not quite as
elegant as Rob's solution but if the RNG was good, I would expect it to work
OK.

Steve

-- 
Steve Revill @ Home
Note: All opinions expressed herein are my own.
0
steve417 (852)
10/17/2007 8:08:01 PM
On Oct 16, 6:09 pm, Nick Roberts <tig...@orpheusinternet.co.uk> wrote:
> The classic implementation of initializing each of the 623 subsequent
> words with 69069 times the previous one is simply applying a fairly
> crude multiplicative congruential RNG to each word.

That method is known to be weak.  See this page:

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html

The BBC BASIC version I posted earlier in the thread uses an improved
initialisation algorithm based on the code here:

http://oku.edu.mie-u.ac.jp/~okumura/cplusplus/mt19937.cc

Richard.
http://www.rtrussell.co.uk/
To reply by email change 'news' to my forename.

0
news1075 (671)
10/17/2007 9:34:41 PM
On Wed, 17 Oct 2007 14:34:41 -0700, Richard Russell wrote:

> On Oct 16, 6:09 pm, Nick Roberts <tig...@orpheusinternet.co.uk> wrote:
>> The classic implementation of initializing each of the 623 subsequent
>> words with 69069 times the previous one is simply applying a fairly
>> crude multiplicative congruential RNG to each word.
> 
> That method is known to be weak.  See this page:

This obviously has ramifications for cryptographic or simulation 
purposes, but for shuffling a deck of cards, I'm not so sure.

B.
0
nntp550 (4244)
10/17/2007 9:57:42 PM
On Oct 17, 10:57 pm, Rob Kendrick <n...@rjek.com> wrote:
> This obviously has ramifications for cryptographic or simulation
> purposes, but for shuffling a deck of cards, I'm not so sure.

Probably not, but the 'improved' method isn't significantly more
complicated so one might as well use it for all applications.  I've
used assembler code because it involves an integer multiplication with
a greater-than-32-bit result, which is messy to do in BASIC.

Richard.
http://www.rtrussell.co.uk/
To reply by email change 'news' to my forename.

0
news1075 (671)
10/17/2007 10:25:38 PM
On Wed, 17 Oct 2007 15:25:38 -0700, Richard Russell wrote:

> I've used
> assembler code because it involves an integer multiplication with a
> greater-than-32-bit result, which is messy to do in BASIC.

Time to extend BBC Basic again, and add something akin to C's long 
long? :)

B.
0
nntp550 (4244)
10/17/2007 10:31:44 PM
Rob Kendrick <nntp@rjek.com> wrote:

> On Wed, 17 Oct 2007 14:34:41 -0700, Richard Russell wrote:
> 
> > On Oct 16, 6:09 pm, Nick Roberts <tig...@orpheusinternet.co.uk> wrote:
> >> The classic implementation of initializing each of the 623 subsequent
> >> words with 69069 times the previous one is simply applying a fairly
> >> crude multiplicative congruential RNG to each word.
> > 
> > That method is known to be weak.  See this page:
> 
> This obviously has ramifications for cryptographic or simulation 
> purposes, but for shuffling a deck of cards, I'm not so sure.

Try asking any of the online gaming companies for an opinion on that :-)

-- 
Stewart Brodie
0
10/18/2007 12:42:02 AM
On 17 Oct, 23:31, Rob Kendrick <n...@rjek.com> wrote:
> On Wed, 17 Oct 2007 15:25:38 -0700, Richard Russell wrote:
> > I've used
> > assembler code because it involves an integer multiplication with a
> > greater-than-32-bit result, which is messy to do in BASIC.
>
> Time to extend BBC Basic again, and add something akin to C's long
> long? :)

Or just write a procedure.

long_a=FNlong_assign(whatever)
long_b=FNlong_assign(whatever)
PROClong_mult(long_a, long_b, long_result)
PRINT FNlong_text(long_result)

--
JGH

0
jgh2 (975)
10/18/2007 6:47:51 AM
On Thu, 18 Oct 2007 00:42:02 +0000, Stewart Brodie wrote:

>> >> The classic implementation of initializing each of the 623
>> >> subsequent words with 69069 times 
>> >
>> > That method is known to be weak.  See this page:
>> 
>> This obviously has ramifications for cryptographic or simulation
>> purposes, but for shuffling a deck of cards, I'm not so sure.
> 
> Try asking any of the online gaming companies for an opinion on that :-)

Are many of their systems written in BBC Basic? :)  I suspect they're 
written in something like Java, which scares me even more.

B.
0
nntp550 (4244)
10/18/2007 9:57:33 AM
On Wed, 17 Oct 2007 18:40:08 +0000, Rob Kendrick wrote:

> On Tue, 16 Oct 2007 18:09:52 +0100, Nick Roberts wrote:
> 
>> An application I had at work had a need for a cycle length of approx
>> 10^60, but unfortunately it also had to be multiplicative congruential
>> (it had to be possible to generate the nth number in the sequence
>> without generating the n-1 numbers in between, and to the best of my
>> knowledge only MC RNGs have this property). That was a monster...
> 
> How random did it have to be?  If it doesn't have to be *that* random, a
> simple solution springs to mind: use a cryptographic hash over counter.

I had a play around with this idea in a quiet moment this morning as it 
amused me to do so.  I'm surprised at how well it works.  My code is 
available from http://www.rjek.com/seedrand.zip (thrown together in 10 
minutes, may be hideously buggy.)

Generating 16MB of random data through it produces the following results 
when fed to a program that analyses the randomness of data:

> Entropy = 7.999989 bits per byte.
> 
> Optimum compression would reduce the size
> of this 16384000 byte file by 0 percent.
>
> Chi square distribution for 16384000 samples is 255.90, and randomly
> would exceed this value 50.00 percent of the times.
>
> Arithmetic mean value of data bytes is 127.5064 (127.5 = random).
> Monte Carlo value for Pi is 3.141744908 (error 0.00 percent).
> Serial correlation coefficient is -0.000128 (totally uncorrelated =
> 0.0).

To me, these results look excellent.  Currently, it just uses MD5.  This 
perhaps isn't the fastest hash in the world, so the performance isn't 
that great.  (Took about 10 seconds to generate 16MB of random values on 
a 2.8GHz Celeron).

This afternoon, I'll talk to my friendly professional cryptographer to 
see if this kind of thing would be safe to use as a seekable stream 
cipher, as that sounds like a superb use for it.

B.
0
nntp550 (4244)
10/18/2007 1:19:09 PM
On Oct 17, 11:31 pm, Rob Kendrick <n...@rjek.com> wrote:
> Time to extend BBC Basic again

Because of the increasing availability of 'true' 64-bit processors I
have given consideration to a version of BBC BASIC with 64-bit
integers and 80-bit floats (it being the convention in BBC BASIC that
'promotion' from integer to float won't reduce the precision).
However compatibility with older versions would be an issue, and it's
never likely to come to fruition.

> and add something akin to C's long long? :)

Even in C you can't efficiently multiply two 32-bit numbers to give a
64-bit result.  You first have to cast the 32-bit numbers to 64-bits,
which is likely to imply a run-time overhead unless the compiler
optimises it out.  It's interesting that while a processor's native
multiply instruction is likely to be 32b*32b->64b (and its divide
instruction 64b/32b->32b) high-level languages almost invariably
insist on the inputs and outputs being the same width.

Richard.
http://www.rtrussell.co.uk/
To reply by email change 'news' to my forename.

0
news1075 (671)
10/18/2007 1:25:26 PM
Rob Kendrick wrote:
> Richard Russell wrote:
> > I've used
> > assembler code because it involves an integer multiplication with a
> > greater-than-32-bit result, which is messy to do in BASIC.
> Time to extend BBC Basic again, and add something akin to C's long 
> long? :)

Just how useful is this? I did implement a long integer for Basalt and
coded a multiplication, but never put it in a published version because
there seemed to be very little /actual/ demand for any of the other new
features, ie I have never had any feedback. ;-)

I have noted Richard's comments on RND and could do something with that,
too.

-- 
 ;  ,', * Basalt * - gives RO 3.10+ versions of BASIC V new and alternative
 ;,'    keywords, dynamic memory for arrays and blocks, new variable types.
 ;',    Legal, fast and simple to use. Freeware - version 0.98� - 19 Aug 03
,;  ',, Steve Drain, Kappa : http://www.kappa.me.uk/basalt.htm

0
steve3677 (307)
10/18/2007 3:42:06 PM
In message <1192713926.520421.260360@e34g2000pro.googlegroups.com>
          Richard Russell <news@rtrussell.co.uk> wrote:

> It's interesting that while a processor's native
> multiply instruction is likely to be 32b*32b->64b (and its divide
> instruction 64b/32b->32b) high-level languages almost invariably
> insist on the inputs and outputs being the same width.

This question probably exposes the chasm of my inexperience.
The use of integer arithmetic in programming seems to me to be
limited, in the main, to
1) representing addresses or offsets between addresses - hence
modulo 2 to the width of the address bus,
2) mathematical packages for number theory or algebra (e.g.
cryptography).
What other important uses, not catered for by floating point
arithmetic, have I omitted?

-- 
Gavin Wraith (gavin@wra1th.plus.com)
Home page: http://www.wra1th.plus.com/
0
gavin4770 (200)
10/18/2007 3:42:30 PM
In message <47165708$0$13932$fa0fcedb@news.zen.co.uk>
       Rob Kendrick <nntp@rjek.com> wrote:

> On Tue, 16 Oct 2007 18:09:52 +0100, Nick Roberts wrote:
> 
> > An application I had at work had a need for a cycle length of
> > approx 10^60, but unfortunately it also had to be multiplicative
> > congruential (it had to be possible to generate the nth number in
> > the sequence without generating the n-1 numbers in between, and to
> > the best of my knowledge only MC RNGs have this property). That was
> > a monster...
> 
> How random did it have to be?  If it doesn't have to be *that*
> random, a  simple solution springs to mind: use a cryptographic hash
> over counter.

It had to be as random as it could be while still maintaining the
nth number generation process.

Multiplicative congruential generators are generally quite good at
satisfying tests for randomness (good ones tend to only fail
dimensional clustering tests, and as my application only actually used
sequences of no more than 4 or 5, failing dimensional clustering
for dimensions > 14, which is where my solution fell down was
acceptable).

-- 
Nick Roberts           tigger @ orpheusinternet.co.uk           

Hanlon's Razor: Never attribute to malice that which
can be adequately explained by stupidity.
0
tigger2145 (262)
10/18/2007 4:44:17 PM
In message <4f335b74f7steve@revi11.plus.com>
       "Ste (news)" <steve@revi11.plus.com> wrote:

> In article <47165708$0$13932$fa0fcedb@news.zen.co.uk>,
>    Rob Kendrick <nntp@rjek.com> wrote:
> > On Tue, 16 Oct 2007 18:09:52 +0100, Nick Roberts wrote:
> >
> > > An application I had at work had a need for a cycle length of
> > > approx 10^60, but unfortunately it also had to be multiplicative
> > > congruential (it had to be possible to generate the nth number in
> > > the sequence without generating the n-1 numbers in between, and
> > > to the best of my knowledge only MC RNGs have this property).
> > > That was a monster...
> > 
> > How random did it have to be?  If it doesn't have to be *that*
> > random, a  simple solution springs to mind: use a cryptographic
> > hash over counter.
> 
> Or use value n to seed a RNG then take the next number that pops out
> of that RNG, assuming that will be the same each time for a given n.
> Not quite as elegant as Rob's solution but if the RNG was good, I
> would expect it to work OK.

That might work, apart from the fact that 'n' could be anything up to
about 10^57.

-- 
Nick Roberts           tigger @ orpheusinternet.co.uk           

Hanlon's Razor: Never attribute to malice that which
can be adequately explained by stupidity.
0
tigger2145 (262)
10/18/2007 4:51:07 PM
In message <1192656881.659653.251570@i38g2000prf.googlegroups.com>
       Richard Russell <news@rtrussell.co.uk> wrote:

> On Oct 16, 6:09 pm, Nick Roberts <tig...@orpheusinternet.co.uk> wrote:
> > The classic implementation of initializing each of the 623
> > subsequent words with 69069 times the previous one is simply
> > applying a fairly crude multiplicative congruential RNG to each
> > word.
> 
> That method is known to be weak.  See this page:
> 
> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
> 
> The BBC BASIC version I posted earlier in the thread uses an improved
> initialisation algorithm based on the code here:
> 
> http://oku.edu.mie-u.ac.jp/~okumura/cplusplus/mt19937.cc

Yep, I'm aware of that, but I did refer to it as "the classic
implementation".

I suspect that the best way to initialise it is to use CryptRandom for
each of the 624 words.

-- 
Nick Roberts           tigger @ orpheusinternet.co.uk           

Hanlon's Razor: Never attribute to malice that which
can be adequately explained by stupidity.
0
tigger2145 (262)
10/18/2007 4:52:47 PM
In message <47175d4d$0$13926$fa0fcedb@news.zen.co.uk>
       Rob Kendrick <nntp@rjek.com> wrote:

> On Wed, 17 Oct 2007 18:40:08 +0000, Rob Kendrick wrote:
> 
> > On Tue, 16 Oct 2007 18:09:52 +0100, Nick Roberts wrote:
> > 
> > > An application I had at work had a need for a cycle length of
> > > approx 10^60, but unfortunately it also had to be multiplicative
> > > congruential (it had to be possible to generate the nth number in
> > > the sequence without generating the n-1 numbers in between, and
> > > to the best of my knowledge only MC RNGs have this property).
> > > That was a monster...
> > 
> > How random did it have to be?  If it doesn't have to be *that*
> > random, a simple solution springs to mind: use a cryptographic hash
> > over counter.
> 
> I had a play around with this idea in a quiet moment this morning as
> it  amused me to do so.  I'm surprised at how well it works.  My code
> is  available from http://www.rjek.com/seedrand.zip (thrown together
> in 10  minutes, may be hideously buggy.)

[SNIP]

My immediate response was "I'm not sure that works", but after thinking
about it for a while, I think it's actually rather a good solution.

It's an /irritating/ solution, 'cos it took a lot of hard work to get
the original generator to work, and hashing a count seems too simple,
but that's mostly a case of "I wish I'd thought of that" than a genuine
complaint 8-)

There are one or two other criteria of the RNG that need to be
satisfied, but I don't think they would do anything other than require
reasonable care in the way it's used.

-- 
Nick Roberts           tigger @ orpheusinternet.co.uk           

Hanlon's Razor: Never attribute to malice that which
can be adequately explained by stupidity.
0
tigger2145 (262)
10/18/2007 5:05:31 PM
On Oct 18, 4:42 pm, Gavin Wraith <ga...@wra1th.plus.com> wrote:
> What other important uses, not catered for by floating point
> arithmetic, have I omitted?

Anything where absolute precision is required, i.e. when the
introduction of an error, however small, is unacceptable.  One obvious
example is any kind of financial (currency) calculation; typically it
is vital that totals are exact: if the two sides of a balance sheet
differ by even a penny (or a cent) the results will be rejected.

Since 0.01 cannot be represented precisely, (binary) floating point
isn't suitable for currency calculations.  Usually one would instead
use an integer number of a small unit such as pence or cents.  Some
languages have a specific fixed-point 'currency' data type to do this
for you.

Try this code in BBC BASIC.  You'll soon see why floating-point isn't
suitable:

      A = 0.00
      REPEAT
        A += 0.01
        PRINT A
      UNTIL FALSE

Richard.
http://www.rtrussell.co.uk/
To reply by email change 'news' to my forename.

0
news1075 (671)
10/18/2007 5:14:30 PM
In message <1192727670.043415.127270@z24g2000prh.googlegroups.com>
          Richard Russell <news@rtrussell.co.uk> wrote:

> On Oct 18, 4:42 pm, Gavin Wraith <ga...@wra1th.plus.com> wrote:
> > What other important uses, not catered for by floating point
> > arithmetic, have I omitted?
>
> Anything where absolute precision is required, i.e. when the
> introduction of an error, however small, is unacceptable.  One obvious
> example is any kind of financial (currency) calculation; typically it
> is vital that totals are exact: if the two sides of a balance sheet
> differ by even a penny (or a cent) the results will be rejected.

Ah yes, money. Well that is definitely not part of my experience!
Are 64 bits sufficient for current accounting practice? Is there,
in fact, a standard which business software is supposed to keep to?
Do traders in different currencies have some abstract unit,
worth incredibly little, independent of any actual currency, for
the purposes of avoiding rounding errors in transactions, or do
they use rational arithmetic?

Thanks.
-- 
Gavin Wraith (gavin@wra1th.plus.com)
Home page: http://www.wra1th.plus.com/
0
gavin4770 (200)
10/18/2007 5:41:49 PM
On Thu, 18 Oct 2007 17:44:17 +0100, Nick Roberts wrote:

>> How random did it have to be?  If it doesn't have to be *that* random,
>> a  simple solution springs to mind: use a cryptographic hash over
>> counter.
> 
> It had to be as random as it could be while still maintaining the nth
> number generation process.
> 
> Multiplicative congruential generators are generally quite good at
> satisfying tests for randomness (good ones tend to only fail dimensional
> clustering tests, and as my application only actually used sequences of
> no more than 4 or 5, failing dimensional clustering for dimensions > 14,
> which is where my solution fell down was acceptable).

Having spoken to a cryptographer, my scheme would be even OK for 
cryptographic purposes if the seed size was 128 bit and the counter was 
always padded to the same length, so you'd just round that up to 128 bit 
too.  I suspect my suggestion would have been a simple solution for your 
problem, although it may have not performed as well, as MD5 is quite 
expensive.

B.
0
nntp550 (4244)
10/18/2007 5:48:21 PM
In message <47168d50$0$13926$fa0fcedb@news.zen.co.uk>
          Rob Kendrick <nntp@rjek.com> wrote:

> On Wed, 17 Oct 2007 15:25:38 -0700, Richard Russell wrote:
> 
> > I've used
> > assembler code because it involves an integer multiplication with a
> > greater-than-32-bit result, which is messy to do in BASIC.
> 
> Time to extend BBC Basic again, and add something akin to C's long 
> long? :)

I've been saying this for several years.  PTR# and EXT# also need
to be 64 bit in preparation for supporting bigger files.

Dave
0
davehigton (2157)
10/18/2007 7:28:23 PM
On Thu, 18 Oct 2007 20:28:23 +0100, Dave Higton wrote:

> In message <47168d50$0$13926$fa0fcedb@news.zen.co.uk>
>           Rob Kendrick <nntp@rjek.com> wrote:
> 
>> On Wed, 17 Oct 2007 15:25:38 -0700, Richard Russell wrote:
>> 
>> > I've used
>> > assembler code because it involves an integer multiplication with a
>> > greater-than-32-bit result, which is messy to do in BASIC.
>> 
>> Time to extend BBC Basic again, and add something akin to C's long
>> long? :)
> 
> I've been saying this for several years.  PTR# and EXT# also need to be
> 64 bit in preparation for supporting bigger files.

Having an OS that supports them is the first step, of course.  And one 
could use such large files without support from BASIC, via SWIs.

But yes, it is something it needs.  I find myself using 64 bit integers 
in C code all the time these days.

B.
0
nntp550 (4244)
10/18/2007 8:34:20 PM
On Thu, 18 Oct 2007 13:19:09 +0000, Rob Kendrick wrote:

> My code is available from http://www.rjek.com/seedrand.zip 

Gah, finger-trouble.  That should be http://www.rjek.com/seekrand.zip not 
seedrand.zip.

B.
0
nntp550 (4244)
10/19/2007 9:49:53 AM
In article <ant1815061cbvM+r@kappa.zetnet.co.uk>,
   Steve Drain <steve@kappa.me.uk> wrote:
> Rob Kendrick wrote:
> > Richard Russell wrote:
> > > I've used
> > > assembler code because it involves an integer multiplication with a
> > > greater-than-32-bit result, which is messy to do in BASIC.
> > Time to extend BBC Basic again, and add something akin to C's long 
> > long? :)
>
> Just how useful is this? I did implement a long integer for Basalt and
> coded a multiplication, but never put it in a published version because
> there seemed to be very little /actual/ demand for any of the other new
> features, ie I have never had any feedback. ;-)

I think the problem is that most stuff you access on RISC OS is <2GB in size
so 32 bits ints are fine (e.g. files and physical RAM). If, however, we
finally got support for big files (>4GB) then you'd absolutely need long
ints.

Steve

-- 
Steve Revill @ Home
Note: All opinions expressed herein are my own.
0
steve417 (852)
10/19/2007 1:05:15 PM
On Thu, 18 Oct 2007 18:05:31 +0100, Nick Roberts wrote:

> It's an /irritating/ solution, 'cos it took a lot of hard work to get
> the original generator to work, and hashing a count seems too simple,
> but that's mostly a case of "I wish I'd thought of that" than a genuine
> complaint 8-)

There's always a simpler solution.  And you're right, it's irritating 
when you think of it after you've put the effort in. :)

B.
0
nntp550 (4244)
10/19/2007 4:32:57 PM
In article <6344cd334f.tigger@bc63.orpheusinternet.co.uk>,
   Nick Roberts <tigger@orpheusinternet.co.uk> wrote:
> That might work, apart from the fact that 'n' could be anything up to
> about 10^57.

When I thought about it, I realised that mine is pretty much the same
suggestion as the one from Rob; put a number into an algorithm which
generates another number which should have as little statistical correlation
to the input as possible. The advantage of a hashing algorithm is that it
can take input from an arbitrarily large bitstream. A 190 bit value might be
a bit large for the average random number generator.

Steve

-- 
Steve Revill @ Home
Note: All opinions expressed herein are my own.
0
steve417 (852)
10/19/2007 8:04:28 PM
On 19 Oct 2007 "Ste (news)" <steve@revi11.plus.com> wrote:
> I think the problem is that most stuff you access on RISC OS is <2GB in size
> so 32 bits ints are fine (e.g. files and physical RAM). If, however, we
> finally got support for big files (>4GB) then you'd absolutely need long
> ints.

Its not absolutely essential. You can manage with an API that uses 
high and low 32bit integers for file positions. BASIC's lack of 
unsigned types does make this a lot more difficult though.

---druck

-- 
The ARM Club Free Software - http://www.armclub.org.uk/free/
The 32bit Conversions Page - http://www.quantumsoft.co.uk/druck/
0
news5843 (7460)
10/19/2007 8:10:16 PM
On Oct 19, 9:10 pm, druck <n...@druck.freeuk.com> wrote:
> Its not absolutely essential. You can manage with an API that uses
> high and low 32bit integers for file positions. BASIC's lack of
> unsigned types does make this a lot more difficult though.

It's worth noting that an ordinary (40-bit) float can contain a 32-bit
unsigned integer *without any loss of precision*, which means you can
use a function like this to convert a 32-bit integer variable to its
unsigned float equivalent:

  DEF FNu(N%) = (N% >>> 1)*2.0 + (N% AND 1)

Similarly this function will convert an unsigned float value to its 32-
bit integer equivalent:

  DEF FNi(N) = ((N / 2) << 1) - (INT(N / 2) <> N / 2)

Richard.
http://www.rtrussell.co.uk/
To reply by email change 'news' to my forename.

0
news1075 (671)
10/19/2007 9:39:10 PM
On Fri, 19 Oct 2007 14:39:10 -0700, Richard Russell wrote:

> On Oct 19, 9:10 pm, druck <n...@druck.freeuk.com> wrote:
>> Its not absolutely essential. You can manage with an API that uses high
>> and low 32bit integers for file positions. BASIC's lack of unsigned
>> types does make this a lot more difficult though.
> 
> It's worth noting that an ordinary (40-bit) float can contain a 32-bit
> unsigned integer *without any loss of precision*

<pedant>Don't you mean accuracy?</pedant>

;-)

B.
0
nntp550 (4244)
10/19/2007 10:32:25 PM
On 19 Oct 2007 Richard Russell <news@rtrussell.co.uk> wrote:

> On Oct 19, 9:10 pm, druck <n...@druck.freeuk.com> wrote:
>> Its not absolutely essential. You can manage with an API that uses
>> high and low 32bit integers for file positions. BASIC's lack of
>> unsigned types does make this a lot more difficult though.

> It's worth noting that an ordinary (40-bit) float can contain a 32-bit
> unsigned integer *without any loss of precision*, which means you can
> use a function like this to convert a 32-bit integer variable to its
> unsigned float equivalent:

You'd be mad to rely on any kind of floating point conversions when 
you need absolute integer precision, even if it works currently.

---druck

-- 
The ARM Club Free Software - http://www.armclub.org.uk/free/
The 32bit Conversions Page - http://www.quantumsoft.co.uk/druck/
0
news5843 (7460)
10/19/2007 10:37:28 PM
In message <1192829950.339612.116580@q3g2000prf.googlegroups.com>
          Richard Russell <news@rtrussell.co.uk> wrote:

> On Oct 19, 9:10 pm, druck <n...@druck.freeuk.com> wrote:
>> Its not absolutely essential. You can manage with an API that uses
>> high and low 32bit integers for file positions. BASIC's lack of
>> unsigned types does make this a lot more difficult though.

> It's worth noting that an ordinary (40-bit) float can contain a 32-bit
> unsigned integer *without any loss of precision*, which means you can
> use a function like this to convert a 32-bit integer variable to its
> unsigned float equivalent:

>   DEF FNu(N%) = (N% >>> 1)*2.0 + (N% AND 1)

> Similarly this function will convert an unsigned float value to its 32-
> bit integer equivalent:

>   DEF FNi(N) = ((N / 2) << 1) - (INT(N / 2) <> N / 2)

> Richard.
> http://www.rtrussell.co.uk/
> To reply by email change 'news' to my forename.

I think we have two slightly different problems.

1  When we need to access information about a file between 2GB and 4GB 
in size, so we need an unsigned 32-bit integer

2  When we need to access file information over 4GB, when we need more 
than 32 bits. Using two integers to access the information then has 
problems if the low integer is signed. The above may help with this, 
but it gets complicated.

Would I be right in thinking that the BASIC OPEN functions would fail 
on a file >2GB? Or is it just that EXT# and PTR# could not be used 
with such files?

-- 
Alan Adams, from Northamptonshire
alan.adams@orchard-way.freeserve.co.uk
http://www.nckc.org.uk/
0
alan.adams (504)
10/20/2007 11:08:20 AM
On Fri, 19 Oct 2007 23:37:28 +0100, druck wrote:

>> It's worth noting that an ordinary (40-bit) float can contain a 32-bit
>> unsigned integer *without any loss of precision*, which means you can
>> use a function like this to convert a 32-bit integer variable to its
>> unsigned float equivalent:
> 
> You'd be mad to rely on any kind of floating point conversions when you
> need absolute integer precision, even if it works currently.

IEE-745 requires absolute accuracy for these whole values.  BBC Basic 
does its own floating point stuff rather than using the FPA11 
instructions, so I don't know if it upholds to that requirement.

B.
0
nntp550 (4244)
10/20/2007 11:15:01 AM
Reply:
Similar Artilces:

US-TX-Austin: Sr. Lead Consultant, Client/Server Visual Basic, ASP, SQL Server; (45338114407)
US-TX-Austin: Sr. Lead Consultant, Client/Server Visual Basic, ASP, SQL Server; (45338114407) ============================================================================================= Position: Sr. Lead Consultant Reference: SMC01419 Location: Austin TX Duration: C-P Skills: Demonstrated leadership exp and the ability to assume a leadership role in a team with minimal supervision. Excellent client relationship skills including negotiation and expectation management. 5+yrs Client/Server and/or Interne...

Does anyone have a spare BBC B Perpex Keyboard Strip?
The perspex keyboard strip from my BBC B has gone AWOL. Does anyone have a spare one that they'd like to part with? I'm in Australia so of course I'll cover postage. :-) Thanks ...

College student needing help with a function....
Hey guys I'm working on a matlab problem for school and I had a couple questions about this function I wrote. It's supposed to use the "divide and average" method to find the square root of a number whether it is positive, negative, or zero and display it with the error. Is there a more correct way to get the answer for the negative square root than just multiplying by 1i in the output rtanderr? Also, this method gives the correct answer when I run it but the format of the answer is weird. This is what it gives me: rtanderr4 = 0 + 2.000000000000000i ...

finding zero of a function
Please, dear friends, how do I find zeros of a function f with constraints, for example f = f(x) solution x: a < x < b tolX = 1d-7 (example) Thank you "Marcio " <marciobarbalho@eq.ufrn.br> wrote in message <gbcu99$e5b$1@fred.mathworks.com>... > Please, dear friends, how do I find zeros of a function f with constraints, for example > > f = f(x) > > solution x: a < x < b > > tolX = 1d-7 (example) How do you find a zero of a function? Had you bothered to try this one simple command: lookfor zero matlab itself would have shown you t...

Timer func: Passing arguments to a function being called by timer() function (not using global)
Hi, I am trying to pass arguments to a function being executed by timer() function. Right now, I am using global variables and it works fine. But is there a way to do it without global variables? Thanks. GS <premgrps@gmail.com> wrote in message <d26b96e2-5e4b-41e4-bed8-0554f0c3259a@p9g2000vbb.googlegroups.com>... > Hi, > > I am trying to pass arguments to a function being executed by timer() > function. Right now, I am using global variables and it works fine. > But is there a way to do it without global variables? The additional argument can be passed in...

pdbsuperpose fails with "Undefined function or method 'procrustes'"
Hello, I'm trying to use pdbsuperpose, but getting odd error messages. Even trying the built-in demos fail with the same errors. For example, when running the "molviewerdemo", the demo starts right but then aborts, like this: EDU>> molviewerdemo initHelixRes = 23 endHelixRes = 34 ??? Undefined function or method 'procrustes' for input arguments of type 'double'. Error in ==> pdbsuperpose>localDoTransform at 394 [d, z, tr] = procrustes(bk1AtomCoords, bk2AtomCoords, 'reflection', doReflect, 'scaling', do...

basic question on register allocation
I have a very basic question on register allocation, the answer to which I cannot find in any textbook. Suppose you have a code that consists of 4 instructions before register allocation, and registers are all virtual, like in SSA format. The first operand is the destination, the remaining two operands are the sources. The architecture I have in mind is a textbook pipelined RISC, like the one you find in H&P architecture books. 1. add R0, R1, R2 2. add R3, R4, R5 3. add R6, R7, R8 4. add R9, R0, R10 Suppose after constructing an interference graph, the register allocator decided R0 must...

[exceptions] no-throw guarantee for trivial functions?
Hello, I try to make more use of exceptions. One question which came to my mind is when to use the no-throw guarantee or not. Consider this: void do_something_harmless() throw() // good practice? { ... } void do_something_harmful_but_will_handle_it() throw() { ... } My feeling is that only functions (and ctors/dtors) whom bodies contain the catch em all statement "catch(...)" i.e { try { /*danger!*/ } /*other catch statements*/ catch(...) { } } should be decorated with throw(). Am I right? Thanks, -- Maik On Jan 14, 1:41=A0pm, Maik <Beckmann.M......

basic programming question
Greetings all, I'm not a programmer, but am a sysadmin for the Mac users in my company. One of our unix programmers (who uses a Mac for her daily work) is starting to program for OSX, and asked me a question that I'll forward to this group. "How does one implement drag and drop in a program?" If this is too incomplete a question, I can ask her for more info. Thanks, DOD dano <dano45@spamcop.net> wrote: > I'm not a programmer, but am a sysadmin for the Mac users in my company. > > One of our unix programmers (who uses a Mac for ...

Basic question, basic answer, nevermind
Had the cables swaped around the wrong way in the back of the Roland :) No worries, most of us have done that. JB "Eddie Crismond" <none@none.none> wrote in message news:vpivv5i09sqpfa@corp.supernews.com... > Had the cables swaped around the wrong way in the back of the Roland > > :) > > "JB Seattle" <shnoozle8@hotmail.com> wrote in message news:lthmb.916$RQ1.602@newsread3.news.pas.earthlink.net... > No worries, most of us have done that. > JB Thanks :) its easy to do. ...

RE: Passing parameters to functions
Thomas Philips wrote: > The following program passes parameters (inluding another function) > into a function. >=20 > def f(myfunc,m=3D3,*numbers): > sumSquares=3Dmyfunc(*numbers[:m]) > print sumSquares >=20 > 1. When I run it, Python gives me the following error message: > Syntax error. There's an error in your program: *** non-keyword arg > after keyword arg The "keyword arg" in your function signature is the arg "m=3D3". Any = args appearing after it must also be given default values, which *numbers doesn't do. My recommenda...

ICT, Computer Science and RaspberryPi on the BBC
ICT, Computer Science and RaspberryPi on the BBC I spotted a 4-5 minute piece all about how the lack of teaching computer science in school is hindering the UK Computer games production market on FREESAT/SKY BBC News Multiscreen (It will probable be there for the rest of today!) They interviewed the head of eidos, google and Dave Braben who demonstrated the RaspberryPi! Some or all of it was apparently shown on Newsnight last night and there is a cut down version available from: http://news.bbc.co.uk/1/hi/programmes/newsnight/9612063.stm More in a blog and a lot of Discussion at http://www....

RE: David's CombinatoricaGraphics functions
Sean, Needs["CombinatoricaGraphics`CombinatoricaGraphics`"] lg = Graph[{ {{1, 2}}, {{2, 3}}, {{3, 2}}, {{3, 1}}, {{1, 4}}, {{1, 4}}, {{1, 5}}, {{1, 5}}, {{4, 5}}, {{4, 2}}, {{4, 2}}, {{5, 2}}, {{5, 2}}, {{5, 4}}, {{5, 4}}}, {{{0.0, 1.5}, VertexLabel -> a1}, {{0.0, 0.0}, VertexLabel -> b2}, {{0.5, 0.75}, VertexLabel -> c3}, {{-0.5, 0.75}, VertexLabel -> d4}, {{-1.5, 0.75}, VertexLabel -> e5}}, EdgeDirection -> On] I would redefine the graph. Maybe there is an easier way to do this. edges = Edges[lg]; MakeGraph[Range[5], MemberQ[edges, ...

Basic questions about the Nios II.
Hello. I'm getting a better outline of what's available and the differences between the different options, such as FPGAs and CPLDs. Although, I've just come across Alteras "Nios II Embedded Processor" and to be honest it's thrown me off completely. - What is a soft-core processor? - It seems that Nios II isn't a physical product I buy, it appears to be an emulator running on top of any FPGA (Stratix, Cyclone etc...)? - Programming the Nios II is done through the Nios II IDE, although this uses C/C++? Is this then converted into a netlist (along with the Nios cor...

Laguerre function
Hi There, I have question in regard to Laguerre function. How can we use this function in Matlab? Can we use Maple's function in Mathlab? Thanks, Maryam Mehdi bahonar wrote: > I have question in regard to Laguerre function. How can we use this > function in Matlab? Possibly this file exchange submission: http://www.mathworks.com/matlabcentral/fileexchange/15916 > Can we use Maple's function in Mathlab? Yes, if you have the appropriate license from Maple to interface with Matlab and you use the right magic calling sequence. Walter Roberson wrote:...

Which function to use for this plot?
I want to make a plot with the following data: X = [12 19 26] Y = [5 22 13] Z = [503 6589 4563] I want to trace z=f(x,y) but not in 3D plot (so I don't want to use plot3 function in matlab) >>help name_of_function please Is this surf? I wait your answers please! Sprinceana wrote: > I want to make a plot with the following data: > > X = [12 19 26] Y = [5 22 13] Z = [503 6589 4563] > > I want to trace z=f(x,y) but not in 3D plot (so I don't want to use > plot3 function in matlab) > >>> help name_of_function please > > Is this surf? >...

Creating True Global Functions by Modifying Builtins
I really, really want a handful of 'true' global functions, ones that can be called from anywhere without requiring importing. So I added it to the 'builtins' of Python, and it appeared to work. :-O Will this have unintended side-effects? :-D Take a look: def traceme(s): print "trace:", s import types def BuiltInFunctions(): callables = (types.BuiltinFunctionType, \ types.BuiltinMethodType, \ types.CodeType, types.FunctionType, \ types.GeneratorType, \ types.MethodType, \ ...

Javascript Functions 32589
I am learning HTML for the first time taking a self teaching class though my local Community College. Normally this college rocks and has some of the best resources and down to earth teachers that pick books that acutally help folks. Well they failed and my book take more logic jumps that Stephen Hawkins! :D So my ultimate question is as follows: How do I created a function with the following information provided: Create a fucntion named Mquote that contains the single parameter, Qnum. My apologies for such little information. I am sure its my oversight that I am unable to locate the answ...

What can C do and Basic V2 not?
I still don�t get it - what is the advantage of C ? I can program anything in BASIC V2 on a C64, does C have any advantages over BASIC V2 ? Seems to be more cryptic than BASIC to me. "Ralf Dieholt" <zaltorlin@yahoo.se> wrote in message news:7a376da1.0402220328.20fdc517@posting.google.com... > I still don�t get it - what is the advantage of C ? Portability, efficiency, readability, in that order. > I can program anything in BASIC V2 on a C64, does C have any > advantages over BASIC V2 ? Yes. > Seems to be more cryptic than BASIC to me. Then use BASIC if you w...

QEngine Web Functional
Hi, New google groups created to share and discuss about QEngine Web Functional testing. And We WELCOME you all to join, share and discuss about QEngine. http://groups-beta.google.com/group/qengine_webfunctional?hl=en Thanks, Anand Hi Anand Thanks for you Info, Whether the qengine support team will answer in this group. Whether we need to pay for the queries asked here, If I not updated yearly support and maintainance, you will answer my questions?. How frequent I will be answered? regards. ...

sampling a function in Matlab
Hello, I'm working on a project where I have a function u(w,p) = log_10(1 + w*log_2(1 + p*a)) - q * w * log_2 (1 + p*a). The variables q and a are constants, and w and p are optimization variables. 'q' is roughly 1.5 and 'a' is around 6 x 10^20. The range of 'w' is 3.1 x 10^9 to 10.6 x 10^9 and the range of 'p' is 0 to 560 x 10^-6. When I plot u(w,p) with respect to w (and keep p constant), the function is concave and it is straightforward finding the maximum w. However, when I plot u(w,p) with respect to p (keeping w constant), because I am subtracting t...

loop basics
hi, I'm learning common lisp using sbcl. To study both the terminal IOs and the loop macro, I started with what I thought would have been easy: a simple echo function within an infinite loop. It looks like this: (defun echo () (loop (format t (read-line t)))) But then definning this at the REPL and then calling (echo), i never get the formatted output. What am I misunderstanding ? -Nicolas On 7 Feb 2007 01:45:25 -0800, nicolas.edel@gmail.com tried to confuse everyone with this message: >hi, > >I'm learning common lisp using sbcl. To study both the terminal IOs >and ...

US-TX-Austin: Glovia Functional Analyst, Data migration/conversion, ProIV; 6-9M (45326032401)
US-TX-Austin: Glovia Functional Analyst, Data migration/conversion, ProIV; 6-9M (45326032401) ============================================================================================= Position: Glovia Functional Analyst Reference: SMC01724 Location: Austin TX Duration: 6-9M Skills: Direct experience in converting to Glovia, specifically: data migration and data conversion. Some technical ProIV expertise Scope: Client currently moving from a legacy ERP system (Chess) to Glovia. They are looking for ...

Proc FCMP
Hi all! =20 I am learning about the new procedure FCMP in SAS 9.2 under Windows. I = use proc fcmp to write my own function NORMAL. I know that there is a = SAS own function NORMAL() which calculates normally distributed random = numbers. But I couldn't use my own function, SAS always uses ist own, = without hint or message in the log =20 Here's the code I used: =20 PROC FCMP OUTLIB=3Dsasuser.funktionen.paket; FUNCTION normal(zahl); RETURN (zahl*2); * simply multiply the value zahl with two; ENDSUB; RUN; OPTIONS CMPLIB=3Dsasuser.funktionen; data zufall; do i=...

looking for a function to draw from an empirical distribution
from historical data that I collected, i divide the data into 100 bins and count the frequency for each bin, and that's my empirical distribution, is there a Matlab function that allows me to draw randomly from that empirical distribution? thanks Luna Moon <lunamoonmoon@gmail.com> wrote in message <cd707e7c-01a4-4649-af1e-0fd10371aa66@w29g2000vba.googlegroups.com>... > from historical data that I collected, > i divide the data into 100 bins > and count the frequency for each bin, > and that's my empirical distribution, > is there a Matlab functio...