A brain teaser

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

A brain teaser

Post by deltarho[1859] »

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 = x
Dim As Byte Ptr z = Cast(Byte Ptr,@y)
  For i As Long = 0 to 6
    Swap z[i], z[xRange(i,7)]
  Next
  x = y
End 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: 12083
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: A brain teaser

Post by fxm »

???
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) + first
End Function

Sub 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))]
  Next
End Sub


Dim AS Ulongint x = 1234567890
Print x
ShuffleUlongint( x )
Print x

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

Re: A brain teaser

Post by Lost Zergling »

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: 12083
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: A brain teaser

Post by fxm »

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) + first
End Function

Sub 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))]
  Next
End Sub


Dim AS Ulongint x = 1234567890
Print x
ShuffleUlongint( @x )
Print x

Sleep
fxm
Moderator
Posts: 12083
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: A brain teaser

Post by fxm »

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


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

Re: A brain teaser

Post by Lost Zergling »

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: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: A brain teaser

Post by deltarho[1859] »

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. Image
fxm wrote:(ByRef -> ByVal, because no obvious assignment of the ByRef passed variable in the procedure body)
That is bad news.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: A brain teaser

Post by deltarho[1859] »

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. Image

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: 12083
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: A brain teaser

Post by fxm »

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

Re: A brain teaser

Post by deltarho[1859] »

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

Re: A brain teaser

Post by Lost Zergling »

'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: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: A brain teaser

Post by dodicat »

Your last shuffle looks OK.
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 20

namespace rr
dim as ulongint a,b,c,d,e
function 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 d
end function
sub init(n as ulongint) 
    a=n:b=n:c=n:d=n
    for m as long=n to n+2
    rndU()+=m
    next
end sub
end namespace
rr.init(timer)
#define irange(f,l)  (rr.rndU() mod ((l-f)+1)) + f

Function 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 &h0000003full
End Function


Sub 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 n
End Sub

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


Function mixup(byval u As Ulongint) As Ulongint
      Union mix
            u As Ulongint
            Type
            As Ubyte b(1 To 8)
      End Type
End Union
Dim As mix m:m.u=u
shuffle(m.b())
Return m.u
End Function


Dim As Ulongint u,r
Do
      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
      Sleep
Loop until inkey=chr(27)

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

Re: A brain teaser

Post by deltarho[1859] »

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. Image

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

Re: A brain teaser

Post by deltarho[1859] »

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: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: A brain teaser

Post by deltarho[1859] »

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. Image

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.
Post Reply