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

Pages: 1-4041-

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.

Name: Anonymous 2009-01-10 15:56

>>32
will take forever to give an answer
Did you miss the part where the answer was given less than an hour after you posted your problem? And it was most likely not seen immediately.

Name: RecursiveFaggot !FROzeN.uHg 2009-01-11 1:24

>>27
Here's one equivalent to my original solution, only much cleaner:

getb a m n nn = mod (nn - n * a) m

solve = [ (a,b,m) | m <- [9585 ..  ],
                    a <- [   1 .. m],
                    b <- [getb a m 6543 6331],
                    b == getb a m 6331 9584,
                    b == getb a m 9584 9025,
                    b == getb a m 9025 3911]

It runs in ten seconds.

>>40
That's not a for loop.  He used HASKELL NOMADS.

Name: Anonymous 2009-02-25 8:19


The code but he   never died in   the first place   elegant expression of   a fundamental type   of logic The.

Name: Anonymous 2009-02-25 8:39

lol @ 'You should be able to solve this'

Name: Anonymous 2009-02-25 9:40

>>43
FrozenVoid is getting better at English!

Name: Anonymous 2009-02-25 20:30

>>45
Please never mention THE FROZEN NAME again!
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 -