Recent

Author Topic: Is there a faster random function?  (Read 9729 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 ) 8)

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

  • Administrator
  • Hero Member
  • *
  • Posts: 2661
    • My Lazarus wiki user page
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

  • Administrator
  • Hero Member
  • *
  • Posts: 2661
    • My Lazarus wiki user page
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  8)

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.
That's extremely helpful.

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.  :D

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
  ADD EAX, Carry       //add previous carry
  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: 1130
  • 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.

Could you please share this one with the logic operations, please?

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: 31
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: 6737
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: 1130
  • 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  :D

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: 686
    • My games in Pascal
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;
  17.   ReadLn;
  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: 5295
    • Bart en Mariska's Webstek
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;
O:-) O:-)

Thaddy

  • Hero Member
  • *****
  • Posts: 14572
  • 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.
bitrate is always calculated like this:sample rate * bitdepth * number of channels.

Thaddy

  • Hero Member
  • *****
  • Posts: 14572
  • Sensorship about opinions does not belong here.
Re: Is there a faster random function?
« Reply #14 on: March 03, 2024, 11:03:37 am »
This means by rough estimate that random eats about 95% of the processing power! :shock:
That can't de unless you call randomize all the time. You should call that just once.
Choose one of the Marsalia randoms that do not use mod.
https://wiki.freepascal.org/Marsaglia%27s_pseudo_random_number_generators
bitrate is always calculated like this:sample rate * bitdepth * number of channels.

 

TinyPortal © 2005-2018