Logo by Sockratease - Contribute your own Logo!

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again

this forum will stay online for reference
News: Check out the originating "3d Mandelbulb" thread here
 
*
Welcome, Guest. Please login or register. July 29, 2021, 04:49:45 PM


Login with username, password and session length


The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!


Pages: [1]   Go Down
  Print  
Share this topic on DiggShare this topic on FacebookShare this topic on GoogleShare this topic on RedditShare this topic on StumbleUponShare this topic on Twitter
Author Topic: Not all random numbers are equaly random  (Read 2435 times)
0 Members and 1 Guest are viewing this topic.
Alef
Fractal Supremo
*****
Posts: 1174



WWW
« on: September 25, 2013, 04:34:43 PM »

After looking at Kerry Mitchell's code...
There are integer random number generator. (alsou by arithmetic means its immpossible to generate a realy random numbers). But then mixing two

formulas or say buddhabrots one needs random numbers of certain range.

I had two formulas, a formula 0 and a formula 1 wich I want to combinate so I somehow must pick 0 ore 1. Having integer random number generator:

 seed = random(seed)

Divided random numbers by fractions of random range (as help files suggest):
int formula= trunc( abs(seed) /(#randomrange/2))

Calculated remainder (a % b = a - trunc(a/b) * b)  (never seen before jet simple as 5 cents):
int formula= abs (seed%2)

Result is very different. First one should be more chaotic like 1,0,0,0,0,1,0 and second should be more equal 1,0,1,0,0,1,0 with two choices result is like

alternation, throught with more choices it should become more chaotic.

***************************************************************************************************************
Then there are buddhabrots generating by iterating random floating point numbers.

  ;area of pixel input. I used width of 5 and height of 4. (flots from 2.5<x<2.5 and 2<y<2)
  float srcMinX = - (@srcWidth * 0.5)
  float srcMinY = - (@srcHeight * 0.5)
  ; generate random integers (-#randomrange to #randomrange)
  irandX1 = seed = random(seed)
   irandY1 = seed = random(seed)

Here we need to convert random integers to random floats.

    ; convert to random float numbers by dividing by random range
    srcX1 = (abs(irandX1) / #randomrange)*@srcWidth + srcMinX
    srcY1 = (abs(irandY1) / #randomrange)*@srcHeight + srcMinY

    ; convert to random float numbers by reminder of division by screen width.
    ; To create random double float numbers I multiplied random integers by Eulers number (#e)
    srcX1 = abs( (irandX1*#e)%@srcWidth )+ srcMinX
    srcY1 = abs( (irandY1*#e)%@srcWidth )+ srcMinY


I think the difference should be as random numbers are tended to form clasters, first formula have high chance to treat claster as one number but the

second formula have a high chance to divide it. However multiplication created another problem seen only in zoom.


p.s.
Escape time fractals with introduced random numbers have interesting properties, small threads and stalks become regions and with very large iteration

values orbits almoust allways find their way to escape.
Logged

fractal catalisator
Alef
Fractal Supremo
*****
Posts: 1174



WWW
« Reply #1 on: September 25, 2013, 04:35:13 PM »

Anyway, first random numbers vs second. Second looks slightly with less random dots.




Lets render something larger without equalisation. Looks the same but at this size single pixels aren't noticable.




Zooming in closer shows that second one indeed have less random dots and barely noticable loss of contrast.



But then I had one old parameter, rough enought and zoomed. First one have something like barely noticable fingerprint threads (fingerprint of random

number generator?) but the second are kind of legs.




Here its more evident:




Anyway, there are haltonian sequences. Or maybe there are some better way to generate random floats in range a<RndF<b. For M3D MonteCarlo Jesse in some post mentioned halton * random, alsou that random numbers improve outcome like result=times^2 and halton result=times^1. So downloaded a lots of .pdf about halton. http://www.fractalforums.com/releases/mandelbuld-3d-v1-8-6-beta-test/45/
« Last Edit: September 25, 2013, 04:52:15 PM by Alef » Logged

fractal catalisator
Softology
Conqueror
*******
Posts: 120


« Reply #2 on: September 25, 2013, 11:44:32 PM »

I use Mersenne Twister to generate random floats for Buddhabrots
http://en.wikipedia.org/wiki/Mersenne_twister
http://softologyblog.wordpress.com/2011/06/26/buddhabrot-fractals/

You get a much longer sequence (period) of unique random numbers before they start repeating.

Jason.
Logged
Roquen
Iterator
*
Posts: 180


« Reply #3 on: September 26, 2013, 09:31:44 AM »

MT is a major red herring unless (maybe...just maybe) you're working on a supercomputer.  The Cray Titan can perform approximately 279 operations per year, so using a PRNG with a period in 2 to the hundreds or thousands is virtually insured to be computation overkill and if it isn't then you know why.  MT is good?  Unmodified it fails some basic stats test of SmallCrush (this is easy to fix...just most people don't know they need to)  MT is fast?  Only in apples to oranges micro-benchmarks.  Recall the saying:  "Lies, Damn Lies and Benchmarks".

But really this is an aside.  The more important question is: what distribution do I want?  All reasonable choices of PRNG are going to be basically equivalent.  LDS seem a much better choice since they give converging coverage.  Blue noise, even with recent advances using Wang Tiling is going to be much more expensive and probably no better than a LDS.
Logged

All code submitted by me is in the public domain. (http://unlicense.org/)
xenodreambuie
Conqueror
*******
Posts: 124



WWW
« Reply #4 on: September 27, 2013, 12:41:41 AM »

MT is a major red herring unless (maybe...just maybe) you're working on a supercomputer.  The Cray Titan can perform approximately 279 operations per year, so using a PRNG with a period in 2 to the hundreds or thousands is virtually insured to be computation overkill and if it isn't then you know why.  MT is good?  Unmodified it fails some basic stats test of SmallCrush (this is easy to fix...just most people don't know they need to)  MT is fast?  Only in apples to oranges micro-benchmarks.  Recall the saying:  "Lies, Damn Lies and Benchmarks".

But really this is an aside.  The more important question is: what distribution do I want?  All reasonable choices of PRNG are going to be basically equivalent.  LDS seem a much better choice since they give converging coverage.  Blue noise, even with recent advances using Wang Tiling is going to be much more expensive and probably no better than a LDS.

I agree, and I think it depends on the context and requirements. For some finite area sampling, precomputed blue noise can give a good combination of speed and quality, but hard to justify for most other uses. For generating huge numbers of samples, one really does need to know what a reasonable choice of PRNG means. Being free of correlations up to the required number of dimensions is important. Less well known are the requirements for lottery uses, specifically the need for all combinations of a given length to occur, and with equal frequency. Most generators fail that test. This is relevant for IFS fractals, and one of the reasons I switched from MT to George Marsaglia's CMWC generators. For progressive sampling of parameter spaces I started using Sobol sequences, because they do converge faster and nicer than random numbers. Even with good scrambling parameters (Joe and Kuo), some dimensional combinations seem to work better than others.
Logged

Regards, Garth
http://xenodream.com
Alef
Fractal Supremo
*****
Posts: 1174



WWW
« Reply #5 on: October 01, 2013, 06:02:38 PM »

Mostly I wanted to improve image quality and I think important charateristic would be more equal distribution, so Low Disrepancy Sequences should be better than better randomness. Wikipedia says that first 256 Halton vs RND numbers.


Realy it aren't as good as dedicated wikipedia article states, not shure why having only two halton sequences x and y failed to generate buddhabrot. (Maybe becouse my buddhabrot script converges on reaching hits on pixels and not iteration cyles?)

Code:
haltonX = 0
form = 0.5
cycle = cnt+34
WHILE (cycle > 0)
haltonX = haltonX + form * (cycle % 2)
cycle = floor(cycle *0.5)
form = form *0.5
ENDWHILE

haltonY = 0
form = 0.2
cycle = cnt+34
WHILE (cycle > 0)
haltonY = haltonY + form * (cycle % 5)
cycle = floor(cycle *0.2)
form = form *0.2
ENDWHILE

Then I generated 4 halton sequences, so that each x and y values were generated by arithmetic mean of two halton sequences. Thats alredy 4D, but it generated orbit plot.
srcX1 = 0.5*(haltonX2+ haltonX)*@srcWidth + srcMinX
srcY1 = 0.5*(haltonY2+ haltonY)*@srcHeight + srcMinY


Having 3 halton sequences for each of x and y is a 6D task and I think buddhabrot slightly detioreted. Wikipedia states, that sobol sequences outperforms halton with large number of dimensions. Not tested.
srcX1 = (haltonX3+haltonX2+ haltonX)/3*@srcWidth + srcMinX
srcY1 = (haltonY3+haltonY2+ haltonY)/3*@srcHeight + srcMinY


Judging from this pure Haltons aren't so practical.


* 1Halton_Fail.jpg (19.68 KB, 320x240 - viewed 644 times.)

* 1Halton_4D.jpg (23.2 KB, 320x240 - viewed 683 times.)

* 1Halton_6D.jpg (20.52 KB, 320x240 - viewed 712 times.)

* 1RND.jpg (25.95 KB, 320x240 - viewed 642 times.)
« Last Edit: October 01, 2013, 06:08:31 PM by Alef » Logged

fractal catalisator
Alef
Fractal Supremo
*****
Posts: 1174



WWW
« Reply #6 on: October 01, 2013, 06:04:59 PM »

Random start or scrambled sounds too theoretical so I generated x and y as arithmetic mean of Halton Sequence and Random Numbers. It improved outcome if compared with pure RND with just insignificant loss of speed, ~10% (and with large hits on pixel maybe faster). Alsou shifting halton sequences does improve looks.
srcX1 = (abs(irandX1) / #randomrange +haltonX)*0.5*@srcWidth + srcMinX
srcY1 = (abs(irandY1) / #randomrange +haltonY)*0.5*@srcHeight + srcMinY

But RND * Halton generated very nice and clear result but distorted mandelbrot so that one side become thicker ( n^2 distorts distribution equality).


Orbit plot of z=tan(z)*z+c and z=z^2 *iter*0.05 +c is interesting. Somehow halton + random generated different shape than pure random. Why? Better spread in range huh?  I think actual shape should be as random + halton as sharp edges for these formulas is higly unlikely.




Fingerprint like threads and net dissapeared. Throught I should say that net was pretty cool even if net is rather unlike orbit.








So I think (Halton + RND)*0.5 could be the best floating numbers when it comes to distribution/price.
Maybe this thing would be usefull, say if you want zoom into your orbit plot fractal.

p.s.
Sobol pseudocode would be nice share.
« Last Edit: October 01, 2013, 06:09:58 PM by Alef » Logged

fractal catalisator
eiffie
Guest
« Reply #7 on: October 01, 2013, 08:37:13 PM »

If you want equal distribution AND know how many samples you want to render then just tile + random/tile width would give a cheap equal distribution. If you are taking 1 mil samples then tile 1000x1000 + random/1000. I know this is too simple but I haven't seen an example of the output. Have you tried?
Logged
Roquen
Iterator
*
Posts: 180


« Reply #8 on: October 03, 2013, 11:16:09 PM »

Look here: https://sites.google.com/site/qmcrendering/

Have a quick peek at "Quasi-Monte Carlo Methods in Photorealistic Image Synthesis" at the "Anti-aliasing and deterministic parallelization" section.

Logged

All code submitted by me is in the public domain. (http://unlicense.org/)
Alef
Fractal Supremo
*****
Posts: 1174



WWW
« Reply #9 on: October 10, 2013, 05:34:47 PM »

Thanks for the link. Downloading.

Tiling is the simplest part, after tiling, you have a random number generator, or maybe a quasi random number generator (Low Disrepancy Sequences) and the result differs.

And the type of random numbers used are important in many aplications. I meant this:
http://www.fractalforums.com/releases/mandelbuld-3d-v1-8-6-beta-test/45/

Quote
Here some more results from the montecarlo pseudo RNG approach:
2 images attached, first the halton numbers and all pixels get the same ones for ambient rays, it is more like many straight reflects...
so i did a way to shift the halton values (also pseudo random) based on the pixel position, what makes it comparable to the random noise generator with the ability of noise filtering!
The benfit is that it seems to converge linear with raycount and not quadratic!
(Or better: noise~1/raycount  versus noise~1/Sqrt(raycount) with standard RNG)...
Correction: this can't be really true, must be a bit different...  huh?

Of course one needs for every depth of calculation and every function (DOF, subpixelshift) independent pseudo numbers, but even only the first depth of ambient calculation brings a big profit.

The second images shows the difference with about 62 calculated rays in average, this makes it really useable!!!


Throught then LDS + RND generates better results. Not shure why RND and (LDS+RND)/2 generated different results and which is the real orbits.  


* Brahmabrot_eye_HaltonRND_640.jpg (79.93 KB, 640x480 - viewed 406 times.)

* Brahmabrot_eye_RND_640.jpg (90.14 KB, 640x480 - viewed 590 times.)
Logged

fractal catalisator
Roquen
Iterator
*
Posts: 180


« Reply #10 on: October 10, 2013, 11:25:27 PM »

Something I should have mentioned is that if your generating LDS samples per pixel/fragment (and using the same set leads to obvious defects) then in the integer computation part you can use a single unique integer per pixel/fragment and XOR that in for each sample component so each pixel/fragment has a unique sequence.

Also there's a tech report from pixar (this or last year) about doing permutations for doing this kind of thing...but in my opinion it overkill in situation like this.

You were asking about sobol at some point...I'll try to figure out where my sobol generator is and post the code.

Err..I guess while I'm babbling...for cheap computation:  Hammersley (not sure of spelling) like sets can give good results...the trick is that you need to be able to decide in advance the number of points you want to generate for a given computation.
Logged

All code submitted by me is in the public domain. (http://unlicense.org/)
Pages: [1]   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
8-bit random (unsigned) Programming David Makin 6 2698 Last post October 06, 2011, 02:53:04 AM
by David Makin
Random thoughts General Discussion Burnart 6 1227 Last post May 02, 2013, 08:02:06 AM
by Burnart
Random colours Movies Showcase (Rate My Movie) Kalles Fraktaler 10 1210 Last post September 02, 2013, 11:27:08 PM
by Kalles Fraktaler
CUDA random numbers for threads Programming kubinator4321 5 863 Last post January 29, 2015, 04:10:13 PM
by ker2x
Better living through random numbers... Fragmentarium Feline 11 753 Last post April 07, 2016, 10:40:47 AM
by Roquen

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines

Valid XHTML 1.0! Valid CSS! Dilber MC Theme by HarzeM
Page created in 0.28 seconds with 24 queries. (Pretty URLs adds 0.015s, 2q)