Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

Author Topic: Is there a faster random function?  (Read 9294 times)

BuffaloX

• New Member
• Posts: 10
Is there a faster random function?
« on: June 23, 2007, 12:32:40 pm »
Is there a faster random for Lazarus/fpc than the default random function.
I only need 32bit integers.

I just did some fast pixel stuff, and I was quite impressed with the performance of TLazIntfImage used with GetDataLineStart.
I got  about 50 MPixels/sec ( 2 Ghz Athlon 64 )

Unfortunately when I wanted to "animate" the pixels with a random colour, performance dropped to 250.000 pix/sec.

This means by rough estimate that random eats about 95% of the processing power! :shock:

I could do a huge array of random numbers, but that seems a bit lame. :oops:

Vincent Snijders

• Hero Member
• Posts: 2661
RE: Is there a faster random function?
« Reply #1 on: June 23, 2007, 01:00:28 pm »
Using a linear congruential random number generator would probably faster, but those generators are statistically weaker. But maybe that doesn't matter in your case.

BuffaloX

• New Member
• Posts: 10
RE: Is there a faster random function?
« Reply #2 on: June 23, 2007, 01:28:19 pm »
It only needs to appear random.
Statistic weakness, missing values, repetition doesn't matter as much as speed.

I've been up all night trying to find something, but I've had no luck.
I thought I could find something meant for games or audio-noise or something where speed is essential.
But I've had no luck so far.

Vincent Snijders

• Hero Member
• Posts: 2661
RE: Is there a faster random function?
« Reply #3 on: June 23, 2007, 09:28:07 pm »
Inspired by the code from the FASTA benchmark, I give this function for generating a random number between 0..138867.
Code: [Select]
`function genRandom: integer;const  seed : integer = 42;  IM = 139968;  IA = 3877;  IC = 29573;begin  seed := (seed * IA + IC) mod IM;  result := seed;end;`

BuffaloX

• New Member
• Posts: 10
Is there a faster random function?
« Reply #4 on: June 23, 2007, 11:19:44 pm »
WOW cool

I didn't know I could make a const, use it ch it and call the function again and reuse the const with the new value.

The function is very fast, i now get 24 Mpixels/sec
Unfortuinately it creates a clearly wavy pattern, but I think I can fix that.

eric

• Sr. Member
• Posts: 267
Is there a faster random function?
« Reply #5 on: June 24, 2007, 08:13:09 pm »
Here's a high quality random number generator using x86 assembler:

VAR
Carry,
RngSeed : LONGINT;

FUNCTION AsmRandInt(Range: LONGINT): LONGINT; pascal;
//returns integer 0..Range-1
{ High quality random numbers based on Multiply With Carry, by prof. Marsaglia
::            x(n)=a*x(n-1)+carry mod 2^32                       ::
The period of the generator is a*2^31-1.
multiplier a can be selected from the following list (any one will do):
1791398085 1929682203 1683268614 1965537969 1675393560
1967773755 1517746329 1447497129 1655692410 1606218150
2051013963 1075433238 1557985959 1781943330 1893513180
1631296680 2131995753 2083801278 1873196400 1554115554
}
CONST
Multiplier : LONGINT = 1791398085;
//  <--EAX  Result
ASM
(* Create next random number *)
MOV EAX, RngSeed
MUL Multiplier       //64 bit multiplication, carry in EDX
MOV RngSeed, EAX     //update seed
MOV Carry, EDX       //update carry, random number generation done

(* Scale the number to 0..Range by doing Seed MOD Range *)
CDQ                  //Make EAX a quad word in preparation for division
MOV EDX,0            //zero EDX in case CDQ went negative
DIV Range            //remainder in EDX...
MOV EAX, EDX         //...which needs to return in EAX
END;

BuffaloX

• New Member
• Posts: 10
Is there a faster random function?
« Reply #6 on: July 03, 2007, 04:31:08 am »
I suddenly stumbled upon an amazingly fast random generator.
It returns a longint and range can not be specified, which is fine, because when doing graphics it's faster to just mask out unwanted bits.

It's called KISS, and it just does some logic operations, no multiplication or division, which make it SUPER fast,
It has passed some quality tests for random generators, including 2D and 3D dispersion or something, with some very nice images of scattered dots.

Unfortunately there was no license included with the code, I suppose it's considered public domain.
But I'll check it out later, just to be sure.

Gustavo 'Gus' Carreno

• Hero Member
• Posts: 1121
• Professional amateur ;-P
Re: Is there a faster random function?
« Reply #7 on: March 03, 2024, 09:08:26 am »
Hey BuffaloX,

I suddenly stumbled upon an amazingly fast random generator.
It returns a longint and range can not be specified, which is fine, because when doing graphics it's faster to just mask out unwanted bits.

It's called KISS, and it just does some logic operations, no multiplication or division, which make it SUPER fast,
It has passed some quality tests for random generators, including 2D and 3D dispersion or something, with some very nice images of scattered dots.

Unfortunately there was no license included with the code, I suppose it's considered public domain.
But I'll check it out later, just to be sure.

While doing the generator for the 1 Billion Row Challenge in Object Pascal, I've found myself in want of a quicker random function, myself.

Cheers,
Gus
Lazarus 3.99(main) FPC 3.3.1(main) Ubuntu 23.10 64b Dark Theme
Lazarus 3.0.0(stable) FPC 3.2.2(stable) Ubuntu 23.10 64b Dark Theme
http://github.com/gcarreno

Lansdowne

• New Member
• Posts: 30
Re: Is there a faster random function?
« Reply #8 on: March 03, 2024, 09:39:27 am »
Ah but how does"amazingly fast" in 2007 compare with "quite ordinary fast" in 2024 ??

MarkMLl

• Hero Member
• Posts: 6688
Re: Is there a faster random function?
« Reply #9 on: March 03, 2024, 09:44:30 am »
Sure: https://xkcd.com/221/

Everything depends on the quality of the random numbers you require, and particularly if the output is graphical quite subtle departures from "true" randomness will be immediately apparent.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

Gustavo 'Gus' Carreno

• Hero Member
• Posts: 1121
• Professional amateur ;-P
Re: Is there a faster random function?
« Reply #10 on: March 03, 2024, 10:01:24 am »
Hey MarkMLI,

Sure: https://xkcd.com/221/

LOL!!! Indeed

Everything depends on the quality of the random numbers you require, and particularly if the output is graphical quite subtle departures from "true" randomness will be immediately apparent.

The challenge requires values for temperature in the range [-99.9, 99.9].

Anything you can suggest?

But I'm not even sure my bottleneck is the random function. Will start a thread about the generator so we don't off-topic on this here!!

Cheers,
Gus
Lazarus 3.99(main) FPC 3.3.1(main) Ubuntu 23.10 64b Dark Theme
Lazarus 3.0.0(stable) FPC 3.2.2(stable) Ubuntu 23.10 64b Dark Theme
http://github.com/gcarreno

Eugene Loza

• Hero Member
• Posts: 677
Re: Is there a faster random function?
« Reply #11 on: March 03, 2024, 10:43:48 am »
Well, the lower quality, the faster. Even something stupid as below can do:
Code: Pascal  [Select][+][-]
1. program Project1;
2. uses
3.   SysUtils;
4.
5. const
6.   Magic = Int64(%0001101011011110010100110111100010010100000110101011010001010101); //  Just a random 64 bit integer, some would work better than others
7. var
8.   I: Integer;
9.   Rnd: Int64;
10. begin
11.   Rnd := GetTickCount64 xor Magic;
12.   for I := 0 to 19 do
13.   begin
14.     Rnd := (Rnd xor Magic) shr 4 + Rnd shl 4; // just a random bitwise operation
15.     WriteLn(Single(Rnd) / Int64.MaxValue * 99.9:2:1);
16.   end;
18. end.
Rewriting it in Assembly can gain another whooping 4% efficiency.

Sorry, was too lazy to duckduckgoogle, there are better versions of this algorithm - providing better randomness + better Magic number. I believe one of them even removes one of the bitwise operations.

And of course 8-bit integers might work faster than 64-bit (not so trivial on 64-bit processor, but still). But they will quickly suffer from repetitivity. So, I'd recommend you rather to go with 32-bit integers which offer higher performance and (not  guaranteed in this or similar algorithms, but guaranteed in others, like XorShift32) 4 billions values repetition cycle.
My FOSS games in FreePascal&CastleGameEngine: https://decoherence.itch.io/ (Sources: https://gitlab.com/EugeneLoza)

Bart

• Hero Member
• Posts: 5290
Re: Is there a faster random function?
« Reply #12 on: March 03, 2024, 10:54:10 am »
Code: Pascal  [Select][+][-]
1. function Random: Integer; inline; {\$ifdef fpc_has_feature_pure}pure;{\$endif}
2. begin
3.   Result := 5;
4. end;

• Hero Member
• Posts: 14377
• Sensorship about opinions does not belong here.
Re: Is there a faster random function?
« Reply #13 on: March 03, 2024, 10:59:20 am »
I wrote lots of them. They are in the wiki. Marsalia randoms and a fast Delphi compatible one.
Object Pascal programmers should get rid of their "component fetish" especially with the non-visuals.