World: r4wp

creating a separate account

The deobfuscating Knuth's random program project is progressing into 
its final stage. It turned out that with getting the results of the 
program the same only the first part of the puzzle got solved. To 
use it in real programs you use the provided ran_arr_next function. 
This involved some pointer aritmetic that is not 100%  supported 
by Red/System. I finally got the function to produce the same results 
as the C version. The downside is it is now quite a mess with pointer 
indeces and other variables, so a lot of cleaning up to do and/or 
rework only using the index on the array approach.

This involved some pointer aritmetic that is not 100%  supported 
by Red/System.
 What is it lacking precisely?

It is just slightly different. The possibility to go back to the 
first element of the array or store that address. :(ran_arr_buf/1) 
would make it a lot easier. 

I already had a lot of help from Peter on this (thumbs up!) and I 
made good progress by now.

I get the pointer of the array and I can go up and down  using + 
and -, this works great, and the pointer is going along with it then 
and I suspect that if I do 
ptr: ran_arr_buf 
and I progress ran_arr_buf by 1 that I progress ptr too.

I now kinda solved it by using an additional variable. When I reach 
a 100, I subtract 100 from the array ran_array_buf to go back. 

Tonight and tomorrow I have some time to clean up my code and I can 
experiment some more. 

It is proven it can be done, but keeping the extra variable is surely 
slowing down compared to C's pure pointer solution.

I suspect that if I do 
    ptr: ran_arr_buf 
and I progress ran_arr_buf 
by 1 that I progress ptr too.


That's a wrong assumption. Those two variables are distincts, so 
each one has its own memory slot. If you change one, that has no 
effect on the other. What is shared there is the pointed memory region. 
So, if you change ran_arr_buf/value, that will affect ptr/value (they 
both point to the same memory location).

my trouble seems to arise from the different roles the array and 
the pointer play in the C code vs the Red/System code. In C the pointer 
is used as indicator for initialisation and signals when a kind of 
reshuffle is required and it points to the next generated value. 
In Red/System the array points to the current/next value and a pointer 
is not needed, and you can no longer use it as before to signal the 
status. This complicates things in this case.

Oh nice effect. array1: 1 2 3 4 5 
m: 2
;;print array/m ;; 2
array1: array1 + 2
;;print array/m ;; 5

it is tricky to move the array pointer around, beware of the dog 
;)

sorry 5 has to be 4 in that example.

You seem quite confused about pointers in Red/System. 


1) There's no "array" as distinct entity in Red/System, but you have 
indexed access, so you can "simulate" arrays to some extent.


2) "In C the pointer is used as indicator for initialisation and 
signals when a kind of reshuffle is required and it points to the 
next generated value." I don't understand this sentence, you should 
stick to C terminology (terms like "signals", "reshuffle" and "generated 
value" are alien to me in a C language context).


3) "In Red/System the array points to the current/next value and 
a pointer is not needed, and you can no longer use it as before to 
signal the status." I don't understand this one either... There's 
no array, only pointers. "to signal the status" has no meaning to 
me...sorry.

I think you have a complicated mental representation of what pointers 
and arrays are in C and Red/System. It's simpler and more straightforward 
than your descriptions. Basically, Red/System pointers act the same 
way as C ones (including "array" support). The only difference is 
the base for indexed accesses (1 vs 0).

Arnold, what you call :(ran_arr_buf/1) is possible and is just

:ran_arr_buf

Sorry, even simpler:

ran_arr_buf

Yes I know, I built one in already, except when you have shifted 
the ran_arr_buf, this one shifts along, but I want to return then. 
So I saved it in a sav_arr_buf to take care of this. All in all because 
I try to stay as close as possible to the original I have some extra 
bookkeeping to take care of. Later today I will clean up the code 
further and hope the smoke clears up ;)

@Arnold I write the Mersenne Twister random function in Red/System 
according to an educational C standard library implementation ( http://code.google.com/p/c-standard-library/source/browse/src/internal/_rand.c
). Hope you find it useful. you can read it from here: https://gist.github.com/qtxie/5831308

Great work XieQ, congrats! Have you checked it against a C version 
to verify that the output is the same, given the same seed number?

Looks good

I see a pattern.. I discovered I new method of software development!

My 'problem' with the Mersenne Twister is/was that if you print the 
integer it is turned into a negative number if the MSB is equal to 
1, the results could be the same, I did not check. Nevertheless it 
has inspired XieQ to work on his version? Nice to see this result 
XieQ! Keep up the good work!

 The Knuth algorythm is very interesting because of the pointers used 
 and I have little experience in pointers so I really learn a lot 
 and I hope to be able to document the differences, explaining it 
 to newbies in the Red language.

Arnold, good idea!

Question, the program needs an array and it is declared using array1: 
as int-ptr! allocate 100 * size? integer!
Then at the end I free this using free as byte-ptr! array1

Is this really necessary. If the program terminates the memory will 
be freed yes?

(Oh by the way don't free the memory when you are not on the starting 
position anymore, it results in an error.)

(Next, the source I sent to the windows environment, compiled there, 
followed by an immediate runtime error. maybe not the latest Red 
version problem again)

A good operating system will free the memory when the process ends, 
but it's a bad idea to not do your own cleanup of memory and other 
resources

Why is this *** Compilation Error: variable has to be initialized 
at root level 
m: 1
rval: 0
while [m <= 111][
    rval: random
    print ["Random nummer: " m " random waarde: " rval lf]
    m: m + 1
]
The line setting rval prevents this warning.

Well you don't know when this is do you?

How do you mean?

The need to make variables known at the root level of the program 
is a limitation of the current Red/System compiler

(I shared my taocp version in the red/randompublic folder)

Okay I mean you do an #include of a random library or other red(s) 
file, then declaration and init is done. Does the programmer need 
to call a random-free-memory function before ending his/her program?

The line setting rval prevents this warning.
 Look at your ` waarde:` declaration in the PRINT block.

The need to make variables known at the root level of the program 
is a limitation of the current Red/System compiler

 Actually, it's not a limitation, it's a design decision based on 
 use cases like this one: https://github.com/dockimbel/Red/issues/84

waarde is the dutch word for value, this is displaying the random 
generated value, it is between double quotes. In the C output I use 
something like " rval= " rval where in the Red/System I used " rval: 
" rval. This is for my convenience to tell both apart when the terminal 
windows look all the same.

It makes sense to circumvent issues like 84 by this method. Good 
to know this, thank you for explaining.

Oops, sorry, haven't see the quotes.

Arnold, setup and cleanup depend entirely on the library you #include. 
Some don't need any, some need setup but no cleanup, some expect 
both

However, this doesn't apply to your code at hand. You allocate memory 
in your program, so you should also free it

After fix some bugs in my Random function, I got the same result 
against the C version with same seed finally.

One bug need to mention:

After doing mod operation, I use the result as index to access the 
array,it's OK in C, but will cause strange behavior in Red/System. 
Because mod will produce 0 and Red/System use 1-base array.
n: c + state-half-size % state-size
Then I modified the code as below to solve this issue:
n: c - 1 + state-half-size % state-size + 1

I also do a benchmark. It's seems too early to do this, but I can't 
contain my curiously ;-)
Produce 99999999 random numbers

Compare to no optimizition C version, the Red/System version is about 
1.3 times slower.
Compare to an optimizition C version, it's about 2 times slower.
Not bad! :-)
More detail: https://gist.github.com/qtxie/5835643

That's impressive XieQ

That speed result is consistent with earlier benchmarks

@Kaj, if I free the memory at the library funtion level then I lose 
the generator state all the time, I expect that not to be the best 
thing for the randomness of the produced numbers. Say I am a programmer 
and I #include the random functions file/lib. Do I need to call a 
random/free function at the end of my program yes or no?

@XieQ you subtract 1 first and then add it back? All indices get 
shifted 1, including the last one. In loops in C it is i.e. j < N 
and in R/S it will be j <= N. 
You meant curiosity not curiously.

XieQ, indeed impressive results, I usually expects current Red/System 
to perform about 4-5 times slower than optimized C.

Now we can generate the random numbers using the random algorythms. 
It is still a long way to make the random function like REBOL's random: 
http://www.rebol.com/docs/words/wrandom.html

Including a /secure that is, there are even other RNG's out there 
suitable for this purpose waiting for their transcoding to Red/System.

Yes the speed indicates there could be a possible bug, but the MS 
code is pretty straightforward and more one-to-one transcodable, 
so it might as well be right.

MS=MT

@Xieq, I have in plan since the beginning to add fast low-level `odd?` 
and `even?` function. When they'll be implemented, that should give 
to your code a little additional boost. ;-)

Anyway, your implementation is a good hint that Red/System 2.0 should 
be able to give us general performances between unoptimized and optimized 
C code.

BTW, Arnold's and XieQ's work, and my own recent struggling with 
1-based Red/System low-level issues are hints that I need to reconsider 
1-base vs 0-base indexing in Red/System. Low-level algorithms are 
not 1-base friendly.