Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

You should be able to solve this

Name: The Silent Wind of Doom 2009-01-09 15:55

A common algorithm for generating pseudorandom numbers is a "linear congruential generator" which uses the following procedure:

1) A positive integer m and two integers a and b between 0 and m−1 are fixed.

2) A seed r(0) between 0 and m−1 is input.

3) After that, numbers are generated by the recurrence r(n+1) = ar(n)+b (mod m).  (So that 0 <= r(n+1) <= m−1).


The following sequence of numbers was generated in this way.

6543
6331
9584
9025
3911

Find a,b, and m.

(crossposted from /sci/, cuz i herd u liek math).

Name: Anonymous 2009-01-09 15:59

a=1
b=2
m=3

Name: Anonymous 2009-01-09 16:00

namefag

Name: Anonymous 2009-01-09 16:05

The Silent Wind of doom strikes without warning.  Like the cobra.  Like the flu.

Name: Anonymous 2009-01-09 16:09

int rand(){
     return 7;
}

Name: BurningAbyss !5PBCunlFJU 2009-01-09 16:43

The assbergers is spreading. We are all tripfags now.

Name: Anonymous !FROzeN.uHg 2009-01-09 16:52

a=9001
b=69
m=14159

hurr

Name: Anonymous 2009-01-09 16:53

>>1
DO MY HOMEWORK

Name: Anonymous 2009-01-09 17:22

>>7
winrar

Name: Anonymous 2009-01-09 17:24

>>7,9

Leave now.

Name: >>7 2009-01-09 17:27

what the fuck did I do?

Name: Anonymous 2009-01-09 17:32

>>7
http://www.forumspile.com/Cookie-Insight.jpg

Name: Anonymous 2009-01-09 17:35

>>7
Explain plz. ¯\(°_o)/¯

Name: Anonymous 2009-01-09 19:05

a=31337
b=8008185
c=▀█▀ █ ▀█▀ ▄█▀

Name: Anonymous 2009-01-09 19:31


░░░░░░░░░░░░░░░████░░
░░░░░░░████████░░░░█░
░░░░░░█▓▓▓▓▓▓▓█░░░░█░
░░░░░█▓▓▓▓▓▓▓▓▓▓░░░█░
░░░░░█▒▒▒░░▒░░▒▒▒▒▒█░
░░░░█▒░▒░░░▒░░▒▒▒▒▒█░
░░░░█▒░▒▒░░░▒░░░░▒▒█░
░░░░█▒▒░░░░▒▒▒▒▒▒▒█░░
░░░░████░░░░░░░▒▒█░░░
░░░█▒▒▒▒▒▓▒▒▒▓▒▒███░░
░░█▒▒▒▒▒▒▒▓▒▒▒▓▓█▒▒█░
░█░░▒▒▒▒▒▒▓▓▓▓▓▓█▒▒█░
░█░░░░▓▓▒▓▓░▓▓░▓▒▒▒█░
░░█░░▒▓▓▓▓▓▓▓▓▓▓▒▒▒█░
░░░█▒▒▒▓▓▓▓▓▓▓▓▓▒▒▒█░
░░█▒▒▒▓▓▓▓▓▓▓▓█████░░
░░█▒▒█▓▓▓▓▓███░░░░░░░
░░░██░█████░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░

Name: RecursiveFaggot !FROzeN.uHg 2009-01-09 19:35

>>13
Eh, it's easy with brute force.
Iterate through reasonable values for (a,m).  Try each step with b=0 and subtract from the actual next element to find what b would work there.  If all the b values are equal, that's you're answer.

Name: Anonymous 2009-01-09 19:36


░░████░░░░░░░░░░░░░░░
░█░░░░████████░░░░░░░
░█░░░░█▓▓▓▓▓▓▓█░░░░░░
░█░░░▓▓▓▓▓▓▓▓▓▓█░░░░░
░█▒▒▒▒▒░░▒░░▒▒▒█░░░░░
░█▒▒▒▒▒░░▒░░░▒░▒█░░░░
░█▒▒░░░░▒░░░▒▒░▒█░░░░
░░█▒▒▒▒▒▒▒░░░░▒▒█░░░░
░░░█▒▒░░░░░░░████░░░░
░░███▒▒▓▒▒▒▓▒▒▒▒▒█░░░
░█▒▒█▓▓▒▒▒▓▒▒▒▒▒▒▒█░░
░█▒▒█▓▓▓▓▓▓▒▒▒▒▒▒░░█░
░█▒▒▒▓░▓▓░▓▓▒▓▓░░░░█░
░█▒▒▒▓▓▓▓▓▓▓▓▓▓▒░░█░░
░█▒▒▒▓▓▓▓▓▓▓▓▓▒▒▒█░░░
░░█████▓▓▓▓▓▓▓▓▒▒▒█░░
░░░░░░░███▓▓▓▓▓█▒▒█░░
░░░░░░░░░░█████░██░░░
░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░

Name: Anonymous 2009-01-09 20:22

>>16
OP here.  I thought I'd picked an m big enough so you couldn't brute-force it, but I guess not.

There is a much better way to solve this kind of problem that works in about ten seconds for any value of m...

Name: Anonymous 2009-01-09 20:55

>>16
How did you find out Frozen's tripcode?

Name: Anonymous 2009-01-09 20:57

What are 'r' and 'ar'?

Name: Anonymous 2009-01-09 21:10

>>20
r is the element in the psuedo-random sequence. It is defined as a function of previous r's, with r(0) being the initial 0

ar = a*r
In maths and CS, the * character is often used to denote multiplcation

Name: Anonymous 2009-01-09 21:10

>>21
initial seed that should say

Name: Anonymous 2009-01-09 21:28

>>16 here. What I hope that you take away from this is that not every programmer needs to be a crazy mathematical genius who knows every algorithm and data structure known to man. A good programmer doesn't even need to be an incredible genius.

What a good programmer needs is the knowledge that they don't know everything there is to know, and that they need to be constantly searching for a better way.

Name: Anonymous 2009-01-09 22:19

The problem isn't that easily solvable for large enough a,b,m(large enough to make bruteforce take a considerably amount of time), but in real world situations where you would need to brute force a PRNG, you would already know a,b and m, and the goal would be to find r(0).

Name: Anonymous 2009-01-09 22:22

>>23
Fair enough, but the ingenuity to come up with something a little more subtle than a brute-force search is frequently helpful as well.


We know:

6543a + b = 6331 (m)
6331a + b = 9584 (m)
9584a + b = 9025 (m)
9025a + b = 3911 (m)

Eliminate b by subtracting successive equations

212a = -3253 (m)
-3253a = 559 (m)
559a = 5114 (m)

Eliminate a from the first two by multiplying the first by -3253, the second by 212, and subtracting.  Same for the next pair:

0 = (-3253)(-3253) - (212)(559) = 10463501 (m)
0 = (559)(559) - (-3253)(5114) = 16948323 (m)

So m has to divide gcd(-10695403, 16948323) = 14159.  Since two of the given numbers are bigger than 14159/2 (or since 14159 is prime), m must be exactly 14159.

Now since gcd(212,14159) = 1, the equation from above:

212a = -3253 (14159)

determines a, and we can solve this to get a = 9001.  Then plug into one of the first 4 to get b = 69.

:P

Name: Anonymous 2009-01-09 22:27

>>25
'gcd(-10695403, 16948323)' should be 'gcd(10463501, 16948323)'

Name: Anonymous 2009-01-09 22:27

solve = [ (a,b,m) | m <- [1 .. 15000],
                    a <- [0 .. m],
                    b <- [0 .. m],
                    9025 == (9584 * a + b) `mod` m,
                    3911 == (9025 * a + b) `mod` m,
                    6331 == (6543 * a + b) `mod` m ]

Sounds like it should work but Haskell has this nasty habit of driving my C2D over 90C when I make it crunch numbers.

Name: Anonymous 2009-01-09 23:49

>>25
YHBT

Name: Anonymous 2009-01-10 1:35

>>27
I've never even looked at Haskell, but I must say that's a fascinating bit of code. Normally, I would use MATLAB for numerical stuff like that.

Name: Anonymous 2009-01-10 2:06

>>27
Why let m only be [1 .. 15000]? Take advantage of Haskell's laziness and have it be the infinite list [1 .. ].
You can then just do take 1 solve to get one result.

Name: Anonymous 2009-01-10 2:27

>>30
True. When I started writing it m was my last variable, so I limited it to prevent trying (0,0,1), (0,0,2) ... into infinity, but it's not needed anymore.

Also, confirming that it does work, although it's expectedly slow as fuck.

Name: Anonymous 2009-01-10 6:04

>>27
>>29
>>30

*sigh*

What kind of aspie is more impressed by a short piece of code that attacks the problem in the most clumsy, hamhanded way possible and will take forever to give an answer (runtime O(m^3)) it than by a neat, tidy mathematical algorithm that gives you the answer in a minute, and wouldn't take significantly longer if the numbers were 40 digits instead of 4.

Name: Anonymous 2009-01-10 6:08

>>32
They program in Haskell which leads to these "optimized" solutions, like C++ which forces OOP down your throat.

Name: Anonymous 2009-01-10 6:54

>>32
For many problems, a working solution is more desirable than the best solution. Programmer time is not cheap you know.

Name: Anonymous 2009-01-10 7:04

>>34
However it could be insignificant compared to runtime penalty for using inefficient code( at the expense of programming time).

Name: Anonymous 2009-01-10 7:42


* g o a t s e x * g o a t s e x * g o a t s e x *
g                                               g
o /     \             \            /    \       o
a|       |             \          |      |      a
t|       `.             |         |       :     t
s`        |             |        \|       |     s
e \       | /       /  \\\   --__ \\       :    e
x  \      \/   _--~~          ~--__| \     |    x
*   \      \_-~                    ~-_\    |    *
g    \_     \        _.--------.______\|   |    g
o      \     \______// _ ___ _ (_(__>  \   |    o
a       \   .  C ___)  ______ (_(____>  |  /    a
t       /\ |   C ____)/      \ (_____>  |_/     t
s      / /\|   C_____)       |  (___>   /  \    s
e     |   (   _C_____)\______/  // _/ /     \   e
x     |    \  |__   \\_________// (__/       |  x
*    | \    \____)   `----   --'             |  *
g    |  \_          ___\       /_          _/ | g
o   |              /    |     |  \            | o
a   |             |    /       \  \           | a
t   |          / /    |         |  \           |t
s   |         / /      \__/\___/    |          |s
e  |           /        |    |       |         |e
x  |          |         |    |       |         |x
* g o a t s e x * g o a t s e x * g o a t s e x *

Name: Anonymous 2009-01-10 7:58

>>36
Where are the "goats" which have sex in this ASCII art?

Name: Anonymous 2009-01-10 12:11

>>37
I lol'd

Name: Anonymous 2009-01-10 13:47

>>32
You expect people to be ``impressed'' by simple math?  Perhaps you should go back to /sci/.  along with your ego

Name: Anonymous 2009-01-10 15:22

>>39
It's not exactly Gauss' Disquisitiones, but it's more interesting than a damn triple-nested for loop.

>>37
I lol'd as well.
Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -