Solved

Need algorithm: gen Pseudo Random Numbers - EXCEPT!

Posted on 2013-06-04
13
577 Views
Last Modified: 2013-06-05
I need an algorithm to generate Pseudo Random Number Sequences - EXCEPT ... the algorithm must only use generic arithmetic functionality available in most programming languages.

Why? Because I need to write code in C#, Android, C++, Objective-C ... such that, if given the same beginning seed all languages will generate the exact same pseudo random sequence of results.

Any one got any idea's?
0
Comment
Question by:volking
  • 5
  • 4
  • 2
  • +2
13 Comments
 
LVL 11

Assisted Solution

by:MajorBigDeal
MajorBigDeal earned 60 total points
ID: 39220840
http://mathoverflow.net/questions/29494/pseudo-random-number-generation-algorithms

static unsigned long
x=123456789,y=362436069,z=521288629,w=88675123,v=886756453;
      /* replace defaults with five random seed values in calling program */
unsigned long xorshift(void)
{unsigned long t;
 t=(x^(x>>7)); x=y; y=z; z=w; w=v;
 v=(v^(v<<6))^(t^(t<<13)); return (y+y+1)*v;}
0
 
LVL 35

Assisted Solution

by:mccarl
mccarl earned 120 total points
ID: 39220856
Most of those languages would have the mathematic constructs to implement many of the PRNG algorithms around. However, if you are after a relatively simple algorithm so that it is easier for YOU to implement, than I would probably be looking at a Linear Feedback Shift Register algorithm. Even Wiki has probably enough info to get you going...

https://en.wikipedia.org/wiki/Linear_feedback_shift_register

All that is required is generic bit manipulations, such as bit shifting, XOR, AND, negation.... should be no problem in any language you are required to use.
0
 
LVL 5

Author Comment

by:volking
ID: 39220859
@MajorBigDeal - I do not think Bit-Shifting (e.g. << and >>) will be a generic arithmetic solution. I could be wrong, maybe you can write four code snippets using Bit-Shifting?

(1) C#:
(2) Android:
(3) C++:
(4) Objective-C:

Fred
0
 
LVL 5

Author Comment

by:volking
ID: 39220867
@mccarl - ROFL ... what you don't know is ... I'm not smart enough to understand the formulas in most Wiki articles ... sigh ...

I know, I should have taken more math in school, but crafts and drama were soooo much more fun.

Fred
0
 
LVL 35

Assisted Solution

by:mccarl
mccarl earned 120 total points
ID: 39220870
All languages use EXACTLY the same syntax, ie. << and >> for bit shifting (BTW, quite easy to find that via Google)
0
 
LVL 35

Assisted Solution

by:mccarl
mccarl earned 120 total points
ID: 39220873
The Wiki article that I linked gives you actual code samples!! And as you can see in general it boils down to pretty much a one liner.
0
Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

 
LVL 5

Author Comment

by:volking
ID: 39220874
@mccarl

P.S. would sure be nice if I could find a job spewing Shakespeare or making pot-holders.

aaaaaarrrrrgggghhhh!
0
 
LVL 5

Author Comment

by:volking
ID: 39220888
@mccarl - okay I'll try using this one - any comments before I jump in? (I'll start with C# since that's one I use often)

#include <stdint.h>
int main(void)
{
    uint32_t lfsr = 1;
    unsigned period = 0;
 
    do
    {
        /* taps: 32 31 29 1; feedback polynomial: x^32 + x^31 + x^29 + x + 1 */
        lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xD0000001u); 
        ++period;
    } while(lfsr != 1u);
 
    return 0;
}

Open in new window

0
 
LVL 35

Assisted Solution

by:mccarl
mccarl earned 120 total points
ID: 39220897
No, that is the code snippet that I would be looking at if I was doing the same as you.

I hope I am not stating the obvious, but do you realise that only line 10 of the above is all YOU need!? The rest of that code is used for checking the "period" of the LFSR.
0
 
LVL 11

Assisted Solution

by:MajorBigDeal
MajorBigDeal earned 60 total points
ID: 39220898
Bit shifting is very generic but no I can't give you "Android" or Objective-C code because I don't know how.  8*)
0
 
LVL 31

Accepted Solution

by:
GwynforWeb earned 290 total points
ID: 39221059
The following pseudo-code snippet will generate a 1000 random values between 0 and 1 for the variable rand. The sequence is determined by the the initial value of seed. The code is easily modified to produce numbers within any range, including integers within a range. This code assumes 16 digit integer representation.

seed=15239;
for (i=0;i<1000;i++){
 seed =(86028157*seed + 142501)%1299689; 
 rand=seed/1299689; 
 print(rand);
}

Open in new window

Or the following if using type int.
seed=43;
for (i=0;i<1000;i++){
 seed =(5171*seed + 142501)%34421 
 rand=seed/34421;
 print(rand);
}

Open in new window

0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 30 total points
ID: 39221974
Any well specified PRNG algorithm would produce the same result regardless of implementation (assuming that it was implemented correctly)
Some more sophisticated algorithms may be difficult to implement on platforms that don't provide support for high level languages or large number arithmetic.
If you are looking for simple algorithms and are willing to sacrifice quality of the random sequence generated, we should ask how far you want to go.
Returning a constant 0 every time is a possible, though unlikely result of a truly random sequence, and should be easy to implement on any platform.
Maybe you want to minimally specify the range of numbers to be returned, and to stipulate that each possible value is returned the same number of times over a specified cycle length?
It would also help to know the maximum size of numbers on which it is easy to perform arithmetic on the minimal platform of which you are interested.
0
 
LVL 5

Author Closing Comment

by:volking
ID: 39223874
@GwenForWeb
That was EXACTLY what I needed. Thanks.

Everyone got points, but Gwen got more.
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

Entity Framework is a powerful tool to help you interact with the DataBase but still doesn't help much when we have a Stored Procedure that returns more than one resultset. The solution takes some of out-of-the-box thinking; read on!
Real-time is more about the business, not the technology. In day-to-day life, to make real-time decisions like buying or investing, business needs the latest information(e.g. Gold Rate/Stock Rate). Unlike traditional days, you need not wait for a fe…
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…
When you create an app prototype with Adobe XD, you can insert system screens -- sharing or Control Center, for example -- with just a few clicks. This video shows you how. You can take the full course on Experts Exchange at http://bit.ly/XDcourse.

759 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now