QBasic / QB64 Discussion Forum      Other Subforums, Links and Downloads
 

 Return to Index  

The less edited, the better.

April 29 2004 at 12:06 PM
ToohTooh  (no login)


Response to Use of a table of pre-calculated RND results to speed up program

 
I sadly stated that Mac modified my pseudo-random table generator tester heavily some like a week ago and that it lacked better performance. I saw that he didn't update his thread with my original code. An educational visit to Bilkent University got in the way and my update was delayed.

As for the edit, there's no logic in putting

"FOR i = 0 TO 255
randomTable(i) = RND * 999
NEXT i",

namely the pseudo-random-table generator code sequence, into the performance calculating block

"startIt! = TIMER
(...)
stopIt! = TIMER
perf! = (stopIt! - startIt!) / 5".

Also the the function

randomNrGen%

in Mac's edit re-DIMs, calls UBOUND stuff at each call, making the things even worse.

My original code goes like the following and it will perform like 5 times better than the traditional RND, but will show a zillion times poorer random distribution.

Have fun,

ToohTooh

PSEUDRND.BAS
'A non-statistical proof(*) on the fast pre-calculated random tables.

'Hope QBasicers learn from those.

'ToohTooh,
' in Istanbul

'-----
'(*) This program aims to explain the time-complexity of an algorithm,
' and has nothing to do with statistics.

'Speed things up
DEFINT A-Z

'Also put a % to force QBX that it *is* integer (to hack a bug in QB 4.5)(*)
'-----
'(*) QBasic 1.1 is the compiler-stripped-out version of QB 4.5 (as Microsoft
' bet) or QB 4.0 (as *I* bet -- QB 4.0's QBX run exactly as fast as
' QBasic's).
DECLARE FUNCTION randomNrGen% ()

'Do what I rambled (!) in the past thread
DIM randomTable(255), maxRandom
maxRandom = UBOUND(randomTable)

'Get a randomizer seed (x0 in the formula)
seed& = TIMER
RANDOMIZE seed&

' Prepare the table at run-time.
FOR i = 0 TO 255
'Define the upper limit (which is 999) here.
randomTable(i) = RND * 999
NEXT i

'Let it begin -- make it a big prime number that is meaningful to QBasic TIMER
' on today's computers.

'Run 5 tests and get the average.

'Test every piece alone and don't put them within another loop because if you
' compiled this at QB 4.0 and higher within a different program, BC may place
' back-loop-pointer (NEXT keyword's pointer) in far memory which will result
' in switching segments (and thus, corrupting our results).

'Why piece by piece? We should see them perform within a block as BC may
' perform some optimizations.

'First off, our traditional RND. We need to explicitly define an upper bound.
startIt! = TIMER
FOR i& = 0 TO 130002: a = RND * 999: NEXT i&
FOR i& = 0 TO 130002: a = RND * 999: NEXT i&
FOR i& = 0 TO 130002: a = RND * 999: NEXT i&
FOR i& = 0 TO 130002: a = RND * 999: NEXT i&
FOR i& = 0 TO 130002: a = RND * 999: NEXT i&
stopIt! = TIMER
PRINT "Traditional RND performance was:"; (stopIt! - startIt!) / 5

'Now the pseudo-random generator.
startIt! = TIMER
FOR i& = 0 TO 130002: a = randomNrGen%: NEXT i&
FOR i& = 0 TO 130002: a = randomNrGen%: NEXT i&
FOR i& = 0 TO 130002: a = randomNrGen%: NEXT i&
FOR i& = 0 TO 130002: a = randomNrGen%: NEXT i&
FOR i& = 0 TO 130002: a = randomNrGen%: NEXT i&
stopIt! = TIMER
PRINT "Pseudo-random performance was:"; (stopIt! - startIt!) / 5

'If you don't live on Mars, pseudo-random's performance will be greater. Even
' if we do *not* define an upper limit in RND test (which is very unlikely
' in real world), the RND would again be slower (give it a try).

'Note, however, that, although this is random enough for many applications,
' for statistical and artificial intelligence simulations, a better randomiz-
' er should be used.

'The point is that, we, again, see the trade-offs of gaining-in-time.

'All the best,
' ToohTooh

FUNCTION randomNrGen% STATIC

SHARED randomTable(), maxRandom

randomNrGen% = randomTable(nextRandom)
nextRandom = (nextRandom + 1) MOD (maxRandom + 1)

END FUNCTION

 
 Respond to this message   
Responses

 Copyright © 1999-2014 Network54. All rights reserved.   Terms of Use   Privacy Statement