## A brain teaser

General FreeBASIC programming questions.
deltarho[1859]
Posts: 3131
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### A brain teaser

This has kept me busy for a few days.

Given a Ulongint I wanted to do a Knuth shuffle on the eight bytes. My first attempt was to use a Sub with a ByRef parameter, but that did not work - the shuffling failed. I tried a variety of themes but to no avail. I gave up and used a Function with a ByVal parameter and, obviously, a return value. That worked, but it didn't sit right with me having a value coming in via a parameter and going out via a return.

I went back to the Sub approach and eventually come up with this:

Code: Select all

`Sub ShuffleUlongint( ByRef x As Ulongint )Dim As Ulongint y = xDim As Byte Ptr z = Cast(Byte Ptr,@y)  For i As Long = 0 to 6    Swap z[i], z[xRange(i,7)]  Next  x = yEnd Sub`

The xRange(i,7) is one of my generators, but it could be Int(rnd_range(i,8)) from the manual.

What got the ByRef method to work was the two statements 'Dim As Ulongint y = x' and 'x = y'.

Effectively then we have switched from a ByRef environment to a ByVal environment, done some work and switched back to a ByRef environment.

At the moment, I not able to describe with any conviction why we have to do that.

Can anyone come up a clear explanation?
fxm
Moderator
Posts: 10449
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: A brain teaser

???
To me it seems to work with this:

Code: Select all

`Function rnd_range (first As Double, last As Double) As Double    Function = Rnd * (last - first) + firstEnd FunctionSub ShuffleUlongint( ByRef x As Ulongint )Dim As Byte Ptr z = Cast(Byte Ptr,@x)  For i As Long = 0 to 6    Swap z[i], z[Int(rnd_range(i,8))]  NextEnd SubDim AS Ulongint x = 1234567890Print xShuffleUlongint( x )Print xSleep`

Perhaps the problem is rather: where does the passed 'x' argument come from?
Lost Zergling
Posts: 450
Joined: Dec 02, 2011 22:51
Location: France

### Re: A brain teaser

I think I have sometimes noticed that on old versions or maybe because of an optimization of the compiler or whatever it is, byref sometimes behaved in byval, maybe randomly. So I got used to writing: x ＝ myfunc (x), to force the implicit reassignment of the byref and remove the ambiguity, and we get a robust code, even when processing lots of datas. Then it would be up to the compiler to make do with its optimizations, and 'damn'.
fxm
Moderator
Posts: 10449
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: A brain teaser

Due to gcc optimization with '-O x' option?
(ByRef -> ByVal, because no obvious assignment of the ByRef passed variable in the procedure body)
Well done gcc!
:-(

Otherwise, try to pass by pointer value:

Code: Select all

`Function rnd_range (first As Double, last As Double) As Double    Function = Rnd * (last - first) + firstEnd FunctionSub ShuffleUlongint( ByVal px As Ulongint Ptr )Dim As Byte Ptr z = Cast(Byte Ptr,px)  For i As Long = 0 to 6    Swap z[i], z[Int(rnd_range(i,8))]  NextEnd SubDim AS Ulongint x = 1234567890Print xShuffleUlongint( @x )Print xSleep`
fxm
Moderator
Posts: 10449
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: A brain teaser

I think if this is confirmed, it would be useful to put a warning sentence on the Compiler Option: -O page of the documentation.

Not confirmed (see following posts).
Lost Zergling
Posts: 450
Joined: Dec 02, 2011 22:51
Location: France

### Re: A brain teaser

Sometimes we pass arguments to a function and it doesn't matter whether the argument will impact or not, but just whether it is as fast as possible. If this is confirmed, could we also imagine a new keyword 'owt' in addition to byval and byref, kwd whose documentation can be viewed on youtube (tm) https://www.youtube.com/watch?v=SEbLL_BtRX4 ?
;-)
deltarho[1859]
Posts: 3131
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A brain teaser

fxm wrote:To me it seems to work with this:

That is the same as my original code, which was failing.

However, my original code is no longer failing.

I will see if I can find a case where it does fail.

Our machines can be very frustrating at times.

fxm wrote:(ByRef -> ByVal, because no obvious assignment of the ByRef passed variable in the procedure body)

deltarho[1859]
Posts: 3131
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A brain teaser

Yours truly wrote:I will see if I can find a case where it does fail.

I have been at it a while but cannot find one.

Lost Zergling used the term "mainly randomly". So, perhaps I could repeat my tests tomorrow and have issues.

As looked at if we have 'ByRef x As <whatever>' we can do this at the head of the Sub body, 'Dim As <whatever> x_ = x', use x_ thereafter and finally x = x_ then we should be safe.

Another thing. When we have ByRef x, what does @x mean - the address of the reference?
fxm
Moderator
Posts: 10449
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: A brain teaser

deltarho[1859]
Posts: 3131
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A brain teaser

Thanks, fxm. That is heavy.
Lost Zergling
Posts: 450
Joined: Dec 02, 2011 22:51
Location: France

### Re: A brain teaser

'maybe randomly', yes. I remember I had no time nor technicity to further investigate, just adapting my way of coding. Nowadays, I didn't see the pb again, so perhaps an old release, or anything else. I get now full of x＝myfunc(x) in my codes and do not dare to change... So far.. Let's remind the proc ＆its cache management is lower level than the compiler, and we can imagine some use cases where byval could be faster than byref (ie cache faster than bus adress). So far, byref ＆ byval are technical spec, 'one way' (ticket) (no modification of passed param or no need to distinguish byref / byval would be conceptual). There might be a conceptual optimization that is 'hidden' by compiler level, and is automated. Question is : would it be worth to give programmer hand on such (very close to low optimization) design problematics ?
probably no at elementary scale..
dodicat
Posts: 7001
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: A brain teaser

I compare with a union method which should be fool proof.
I use a 64 bit generator to test with 64 and 32 bit compilers (1.08 of course)

Code: Select all

`screen 20namespace rrdim as ulongint a,b,c,d,efunction rndU() byref as  ulongint   e = a - ((b shl 7) or (b shr (57)))   a = b xor ((c shl 13) or (c shr (51)))   b = c + ((d shl 37) or (d shr (27)))   c = d + e   d = e + a   return dend functionsub init(n as ulongint)     a=n:b=n:c=n:d=n    for m as long=n to n+2    rndU()+=m    nextend subend namespacerr.init(timer)#define irange(f,l)  (rr.rndU() mod ((l-f)+1)) + fFunction popcount64(x As Ulongint) As Ubyte      If x=&hffffffffffffffffull Then Return 64      x -= ((x Shr 1) And &h5555555555555555ull)      x = (((x Shr 2) And &h3333333333333333ull) + (x And &h3333333333333333ull))      x = (((x Shr 4) + x) And &hf0f0f0f0f0f0f0full)      x += (x Shr 8)      x += (x Shr 16)      x += (x Shr 32)      Return x And &h0000003fullEnd FunctionSub shuffle(a() As Ubyte)      #define range(f,l)  (rr.rndU() mod ((l-f)+1)) + f      For n As Integer = Lbound(a) To Ubound(a)-2            Swap a(n), a(range((n+1),Ubound(a)))      Next nEnd SubSub ShuffleUlongint( ByRef x As Ulongint )Dim As Ulongint y = xDim As Byte Ptr z = Cast(Byte Ptr,@y)  For i As Long = 0 to 6    Swap z[i], z[iRange(i,7)]  Next  x = yEnd SubFunction mixup(byval u As Ulongint) As Ulongint      Union mix            u As Ulongint            Type            As Ubyte b(1 To 8)      End TypeEnd UnionDim As mix m:m.u=ushuffle(m.b())Return m.uEnd FunctionDim As Ulongint u,rDo      u=irange(0,18446744073709551614)      Print Bin(u);Tab(70);popcount64(u);" ones",u;" number"      r=mixup(u)      Print Bin(r);Tab(70);popcount64(r);" ones",r;" union mix"      shuffleulongint(u)      Print Bin(u);Tab(70);popcount64(u);" ones",u;" pointer mix"      Print "__________________________________________________________"      Print      SleepLoop until inkey=chr(27) `
deltarho[1859]
Posts: 3131
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A brain teaser

Thanks, dodicat.

Interestingly, I found that ShuffleUlongint to be about 3.5 times faster than mixup. However, since they are both very fast and only used once per seed for seed shuffling, for example, that is academic. Of course, it would be a different story if we were going past either millions of times. Off hand, I cannot think why anyone would want to shuffle millions of Ulongints.

I am a fan of readability. mixup has a good edge on ShuffleUlongint.
deltarho[1859]
Posts: 3131
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A brain teaser

I should mention that my opening post refers to the shuffle failing. What happened was when the original Ulongint, when looked at as eight bytes, had some bytes which were not in the shuffled Ulongint. A failure was not obvious when looking at 64 bits without a break.
deltarho[1859]
Posts: 3131
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A brain teaser

There is something else that I did, and I should mention it to save dodicat some time if he thinks of doing the same.

I forced both his union method and my method to use the same initial conditions and FB's random integral number code.

I called the output from both methods 'a' and 'b' and did this at the end of an infinite loop: ' If a <> b Then Print "Ouch" '. This saved me from losing my eyesight comparing 64 bits without byte breaks.

Just bashing the enter key until I was gagging for a cup of tea, I could see many parameters being passed and never saw 'Ouch' once.

Better idea was a For/Next loop and an 'Exit For' if 'Ouch' got printed. A 10 million loop count took nearly nine seconds and no 'Ouch'.

This was also a golden opportunity to test my method without the 'ByRef saftety net'; that is my original code which failed. No 'Ouch' there either. This thread was started because of an issue which seems to have vacated. I wish I had noted the precise times certain events took place because during this period my PC started 'playing' up following a MS optional update. By playing up I mean several applications were bringing up Help files after loading and I had a job closing them and the applications. WinFBE told me it couldn't find a Help file; I didn't ask for one. Eventually, I restored to a full system backup. Needless to say, I have ignored MS inviting me to install the optional update. Was the issue related to my PC 'playing up'? Who knows? Thank goodness, I do a full system backup every day.

fxm and Lost Zergling may have spotted a weakness in gcc's optimization, but that is beyond my pay grade to get involved in that.