Little explorations with HP calculators (no Prime)

[Csaba Tizedes]

(03-31-2017 08:33 PM)pier4r Wrote:  What the function does is the following.
- Given this matrix http://i.imgur.com/moh6eSP.png
- produce a random value between 1 and 7225, call it curProbV
- from the first row to the last row of the matrix, check if curProbV is smaller that the element in the first column (I thought I could start from the bottom, but since curProbV is random, it would not matter).
- if you find that the value is smaller, take the third element in the row and return it.

Simple change the two coloumns (x will be -400, -375, -350, ...; and y=25, 75, 150, ...), and fit a function:

For example, this kind functions fits well(?), but you must to play with the constant values in each equation for the better fit:

an logistic model: (Max-Min)/(1+EXP(-X/F)), where Max~7225, Min~25, F~100 or
a periodic model: (Max-Min)/2×SIN(X/P×PI)+Aver, where P~850, Aver~3625.

Maybe you must to make a little modification on y values, for example shift the data -12.5 for better fit, or change the interval from -400...+400 to -425...+425, as you can see above.

Good luck!
Csaba

[pier4r]

@david m: as long as the difference between steps is close to 25 (say +/- 5),then it is all fine . Thanks again for the hint.

Thanks also csaba for the hint!

I'll check ASAP.

[DavidM]

(04-02-2017 08:34 AM)pier4r Wrote:  as long as the difference between steps is close to 25 (say +/- 5),then it is all fine .

If there's a need for the variance result to be stepped, it can easily be rounded.

To see how much of a difference this would make, I took your latest version and made the following changes:

1) I enabled TEVAL in maintimed to get the final elapsed time
2) getVarFunc was replaced with the following:

Code:

  getVarFunc
  \<<
    @ obtain a random curProbV, leave on stack
    \<-maxSumProbV RAND * 1 + IP

    @ apply variance formula based on range
    IF
      DUP 3826 <
    THEN
      0.53 ^ 5.4 *
    ELSE
      7250 SWAP - \v/ 7.3 *
    END

    @ round resulting variance to nearest 25
    25 / 0 RND 25 *

  \>>

3) The getVarFunc profiling was disabled in matchResFunc so that true impact on performance could be seen

Executing maintimed on my 50g then completed in about 28 seconds. That's obviously a significant improvement, but I'm not certain whether computing the variance in this way has other ramifications. If it's OK, hopefully this brings the app performance back into a reasonable range.

[pier4r]

woah 28 seconds. I have really to check. Interesting inputs!

[DavidM]

Your application makes good use of lists, and as such it strikes me that there could be some good opportunities to use the built-in list processing features of RPL in certain spots. These features can sometimes simplify the coding of a program, though in my experience they don't usually help much in terms of performance.

In your program, one procedure I noticed seemed to be a good candidate for simplification using list functionality: the updWinList procedure.

I believe the following version of this procedure does the same thing as yours, but uses list processing methods instead of manual looping. In this particular case, it also performs slightly faster, but just barely.

List processing features are sometimes very difficult to conceptualize when reading code. I would recommend stepping through this in DBUG mode to get a better idea of what's happening.

Code:

  updWinList
  \<<
    @ program that updates the winner list given the
    @ last tournament result list (in stack level 1 on entry)

    @ determine maximum value of tournament result list
    DUP \<< MAX \>> STREAM

    @ create a new list with the maximum value in each position
    OVER SIZE NDUPN \->LIST

    @ use the above list to make a new one containing 1's
    @ in each position that matches, 0's in others
    \<< == \>> DOLIST

    @ ADD the winning positions to the finalTournResList
    finalTournResList ADD 'finalTournResList' STO
  \>>

[pier4r]

So, yesterday I was trying to find an approximation of the curve on my own. At the end, since I know how I constructed the triangle, I observed the following: http://i.imgur.com/X77UzuM.jpg

Then, since the solution to the quadratic formula was not so compact, I compared the result to the ones of DavidM, in the range 25-3825, and they are incredibly fitting!

I wonder how DavidM was able to get that formula. I tried to use the "fit formula" on the hp 50g but many options gave errors since the X was negative and the fit is done with logarithms. Anyway I suppose it was a power fit with the X moved in a positive domain. so -400 is actually 0 or so. I did the same for the comparison.



for newcomers: for this I made the equations with EQW, saved them in a list, used "0 \->GROB" on the stack, moved the picture file on the pc, used "grob2bmp -b -l original_pic.hp output.bmp" on the command prompt (for grob2bmp see hpcalc.org ) . Then this list has to be stored in the variable 'EQ' to plot more than one equation at time.







The curves are almost the same. Neat!

So, implementing now if I don't get interrupted.

[pier4r]

(04-02-2017 06:19 PM)DavidM Wrote:  Your application makes good use of lists,...

Thanks for the tip. I saw something like DOSUBS and so on but I did not dive in them, I'll check once I fix the variance.

While I still do not know how you got the fitting formula, I understood that you did not try to correlate the 1st and 3rd column of this matrix, but the 1st and the 2nd.

That would be even better actually, then I have the underlying X and I can extrapolate the "variance modifier" as I want. Just I have to fix the program a bit.

edit: fitting the data between column 1 and 2 (the 1 as X, the 2 as y), with power fit I get a value very near to yours.
\( 4.5 \cdot \tt{curProbV}^{0.55} \)

For the other part of the curve, having the sum of probability tokens as X and as Y the variance of the second part of the triangle distribution (so, variance between 25 and 400) I found this with power fit (note that the longer equation is the exact solution).
Getting the functions: http://i.imgur.com/vXdXvzk.jpg









Once again, pretty close, but this time one was not just almost perfectly the other.

[DavidM]

(04-03-2017 08:52 AM)pier4r Wrote:  While I still do not know how you got the fitting formula, I understood that you did not try to correlate the 1st and 3rd column of this matrix, but the 1st and the 2nd.

You are correct, and I hadn't noticed until now that I was using the wrong column! All due to a single digit typo in a regex expression I used to clean up the table (I didn't want to re-type all the values). I'm glad you took the time to double-check. Hopefully my mistake didn't cause too much confusion.

My method of fitting the curve was far less scientific than may be appropriate, which is why I was concerned about its efficacy. In a nutshell, it was:

- Used Excel to plot the data, observed that it was (roughly) a power curve reflected horizontally
- Taking left side as first range, asked Excel to show the power trendline formula
- Tweaked the formula slightly to more closely align the value at 3825 (to bring it closer to 425)
- "Reflected" new x-values (7250-x), then plotted right half
- Repeated the trendline-tweak for that range, with the same focus on the value at (new) x-value 3425 to re-align the peak

(04-03-2017 08:52 AM)pier4r Wrote:  That would be even better actually, then I have the underlying X and I can extrapolate the "variance modifier" as I want.

Then perhaps my mistake was a "happy accident". At the least, it showed the performance increase of the overall process when replacing the table look-up with a computation. Glad you caught the mix-up when you did!

[pier4r]

All fine, thanks for sharing the methof of best fit (I just asked the 50g). Now after some unexpected interruptions I'm hoping to continue the implementation so I can post some results ASAP.

[pier4r]

(04-02-2017 04:01 PM)DavidM Wrote:  ...

So, I modified the code a bit, after some work (you can see it in the previous post) but the direction was very nice. In short "do not access a matrix, especially in algebraic notation', it is super fast now (also due to set flags) compared to before.
2 executions needs 65 seconds only so I would estimate that 1000 needs, 30k seconds, so less than a day.

The 50g can burn that long.

The next post will be about the list suggestion.

Code:


getVarFunc
  @ see log 20170403
  \<<
    @program to extract the variance out of the built matrix
    @the original from hpmuseum.org/forum makes uses of the stack a bit more
    @so it is faster. I changed a little bit.
  
    @output, the variance of the strength points out of the matrix

    0 @curProbV
    0 @tmpV
    0 @sumProbV
    \->
    @external inputs
    @local var
    curProbV
    tmpV
    sumProbV
    \<<
      @ obtain a random curProbV
      \<-maxSumProbV RAND * 1 + IP 'curProbV' STO

      @ now, thanks to the formula of davidM, we get the underlying probability tokens
      @but not the variance modifiers. I modified it to have practically the variance
      @modifiers already, but some moving along the axis is needed.
      @ see the topic linked in the log.
      IF
        curProbV 3826 <
      THEN
        curProbV 0.53 ^ 5.4 * 
        @ 5.4 * x ^0.53
        @ this is almost good in returning the variance, 
        @ but it returns positive values, so we need to move
        @ those back by -425
        425 -
        'tmpV' STO
      ELSE
        7.62 -16 ALOG * curProbV 4.58 ^ *
        @ 7.6 * 10^-16 * x ^4.58
        @ this is good by itself.
        'tmpV' STO
      END
      
      
      @ round resulting variance modifier to nearest multiple of 25
      tmpV 25 /
        @divided by 25 first, so the result will have a decimal part
      0 RND
        @decimal part disappear, now the number is a multiple of 25
        @rounded to the nearest multiple
      25 *
        @now it is the nearest multiple of 25.
    \>>
  \>>

[pier4r]

(04-02-2017 06:19 PM)DavidM Wrote:  Your application makes good use of lists,....

So while I will check your suggestion, the part that you used as example is repeated a tiny fraction of times in the entire procedure (although you made it pretty fast). I definitely need to try to use more STREAM and operations with lists and DOSUBS. The problem is as usual, first be correct, then be correct and fast.

Actually the most executed part, that I suppose is pretty inefficient, is to increase the value in a list. This is executed at least 480 times for main iteration. So for 1000 iterations it is 480k times.

for the moment I have this.

Code:


IncListElFunc
  \<<
    @ program to increase the value of element in a list
  
    @ input on the stack see variables
    
    @output, the list in input, modified, on the stack
    \->
    @external inputs
    lList 
      @list
    lPosV 
      @position of the element
    lincV 
      @increase
    @local var
    \<<
      lList lPosV
        @placing list and position on the stack
        @for storing, later.
      lList lPosV GET
      lincV +
        @getting the value and increasing it
      PUT
        @putting the increased value back
    \>>
  \>>

Now with an approach similar to yours and with operations between lists or STREAM or DOSUBS, I would need only to find a proper approach.

Actually I may do a sequence of 0 with NDUPN, then replace (with ROLLN or something similar) the value on the stack in the wanted position, then create the list and add the new list to the given one.

Does someone have a better way?

[DavidM]

(04-03-2017 05:05 PM)pier4r Wrote:  All fine, thanks for sharing the methof of best fit (I just asked the 50g).

I've got limited experience with fitting curves, but have used Excel several times to do it so I tend to gravitate in that direction. I like being able to quickly tweak the x and y values to see how I can manipulate things for a tighter fit. I didn't spend a lot of time on this one (as you can tell ).

Using the same approach, I took another look at the table and came up with a different formula (using the proper column of data this time) for the curProbV values <3826 which is an even tighter fit (all values from the function are within 0.5 of the table): \[variance=(6.8826\cdot curProbV^{0.5025})-435\]

Though not quite as tight (max delta 1.08), this formula is fairly close for the >3825 inputs: \[variance=416-(7.426\cdot(7230-curProbV)^{0.4953})\]

Despite the closeness in fitting (\(R^2\) is 0.9999 or better in both cases), the question still remains as to whether rounding and/or ceiling the results will provide a useful replacement for the table lookups. Hopefully these (or something like them) will give you what you need!

[pier4r]

(04-03-2017 06:50 PM)DavidM Wrote:  Despite the closeness in fitting (\(R^2\) is 0.9999 or better in both cases), the question still remains as to whether rounding and/or ceiling the results will provide a useful replacement for the table lookups. Hopefully these (or something like them) will give you what you need!

Thanks once again. Already your first function of the two posted was great, I'll check those of yours.

My need is not so strict, what I need is: I would like that a certain variance modifier appears more than other modifiers, so I put probability tokens in the middle (little modifiers) rather than on the tails, like a triangle. The ideal would be a gaussian bell but that's too refined.

So, since rounding makes things ok for the interval steps of 25 units between two modifiers, the problem can happen only if an approximate formula gives too much chances to a modifiers that should not have that much. But if the approximate formulas are pretty tight, since we are talking about thousands of units (I choose large amounts on purpose), then it should be fine. Anyway I'll test once I have the calculations with the modification finished.

Could be a nice side exploration.

[DavidM]

(04-03-2017 06:47 PM)pier4r Wrote:  ...the part that you used as example is repeated a tiny fraction of times in the entire procedure (although you made it pretty fast). I definitely need to try to use more STREAM and operations with lists and DOSUBS. The problem is as usual, first be correct, then be correct and fast.

I agree. My example wasn't intended to be focused on performance, but rather to show some of the power of RPL's list processing. The slight bump in performance was nice, but not the reason I explored the alternate version of the function.

My own thought process defaults to an iterative approach to processing the elements of a list (as opposed to thinking about them as a single object), so I have to remind myself to look for opportunities to make good use of the list processing features of RPL. That particular procedure took a list as input, and then stored the result in the same format. So it seemed a good candidate to practice coding for lists. I usually find that forcing a list-based data model on top of something that started off as something else loses all the advantages. This was a good example of when everything was in sync, so it worked well.

(04-03-2017 06:47 PM)pier4r Wrote:  Actually the most executed part, that I suppose is pretty inefficient, is to increase the value in a list. This is executed at least 480 times for main iteration. So for 1000 iterations it is 480k times.

for the moment I have this.
[...]

Actually I may do a sequence of 0 with NDUPN, then replace (with ROLLN or something similar) the value on the stack in the wanted position, then create the list and add the new list to the given one.

I'm doubtful that would perform any better in this situation. Part of the problem here is that there's a fair amount of system overhead in dealing with the discrete elements of RPL lists, no matter how you approach it. Internally, the contents of lists are always accessed sequentially because there are no indices/offsets maintained for each discrete object. So any time you read or write an individual list element, the system has to traverse each and every element that precedes it in the list to find it's location. Making a change to a specific element requires rebuilding the entire list. In this case, you'd actually be adding yet another list traversal to each iteration of your loop (so that you could ADD it).

I know that you are still warming up to the idea of using the stack for temporary data storage within RPL programs, but it's probably one of the only UserRPL ways that you would be able to speed this up. More specifically, I'm referring to exploding the rrResList elements onto the stack before starting the inner loops, using ROLL/ROLLD to update the stack-based team values while in the loops, then ->LIST after the loops are completed before storing the new rrResList.

As it stands right now, your innermost loop recalls, explodes/rebuilds (implicitly), updates an element, and stores rrResList in each iteration. All but the update could be moved out of the inner loop by leaving the list contents on the stack while the loop executes.

[pier4r]

(04-03-2017 09:59 PM)DavidM Wrote:  I know that you are still warming up to the idea of using the stack for temporary data storage within RPL programs, but it's probably one of the only UserRPL ways that you would be able to speed this up. More specifically, I'm referring to exploding the rrResList elements onto the stack before starting the inner loops, using ROLL/ROLLD to update the stack-based team values while in the loops, then ->LIST after the loops are completed before storing the new rrResList.

As it stands right now, your innermost loop recalls, explodes/rebuilds (implicitly), updates an element, and stores rrResList in each iteration. All but the update could be moved out of the inner loop by leaving the list contents on the stack while the loop executes.

Once again, thanks for the hint. I may do little programs just to collect the stack operations and so to isolate them and make them very small.

I'm against the stack operations not because I don't like them. in 2012 and 2013, when I used more the 50g, I used to do a lot fo operations stack only. I was so convinced that was a principle to avoid mostly any variable. I just had to keep track of the stuff created and moved via comments.

Then I saw those programs some months ago, and were like korean. The same impression of the linked solution of Gerson (he skillfully makes use of the stack). If the operation are few, then it is mostly no problem, like 4-5 commands one after another that could be isolated. Otherwise they hinder the maintainability for others (or just for myself for the future) and therefore it is not worth it. If I cannot achieve good performances without heavy use of the stack, while using the stack is quite a mental training (it is not that I dislike it), I decide to move the problem on a different platform.

It is, how can I say, a code principle for myself. It would be a better solution to try hpgcc instead of a heavily stack based program in userRPL, in terms of man hours at least.

[pier4r]

So, 1000 iterations for the double round robin format completed in 34 thousands seconds (so, a night ). The results are: { 0 0 0 0 0 1 0 1 3 6 27 59 112 177 334 503 } (note 1) in other words, the teams with top strength (at the end of the list) wins most of the time, although strength modifiers would allow in theory to let even the weakest teams to win. I will use this result to see how other formats behave.

But before that, some comparison about the formulas to approximate the cumulative probability for variance modifiers. Or maybe, let's do it later now that most of the program work in reasonable time.

note 1:
teams base strength {1225 1250 1275 1300 1325 1350 1375 1400 1425 1450 1475 1500 1525 1550 1575 1600} , http://i.imgur.com/moh6eSP.png column 2 probability tokens for the strength modifiers in column 3.

[pier4r]

I hope to finish this simulation quickly, since I miss solving some brilliant problems, they were a more intense but smaller endeavor and moreover pushed in different directions with a lot of math.

So now for the swiss tournament format (or also the knockout format) I need to shuffle a list. For my searches I did not find anything for it on the AUR or on this forum.

The first idea that I have is the following:

- given a list
- go through it with the STREAM command using the following program
-- get the previous element and the new element from the list
-- get a random number, the new element would be on the stack L1 if the random number is less than 0.5, otherwise on L2, while the previous element on L1.

So it would be like a bubble sort, but actually being a bubble shuffle.


Second idea, using the - for me difficult to visualize and therefore possibly chaotic - stack operations.

- given a list
- explode it
- save the number of elements
- for a certain number of iterations, take a random integer between 1 and the number of elements in the list, then execute ROLL (or ROLLD)
- build back the list.

Does someone knows if better implementations were already done in userRPL? If yes, links or clues would be appreciated.

[DavidM]

Joe Horn wrote an article (located here) where he discusses a couple of different methods of simulating die casts and shuffling.

I've used a similar technique a couple of times for randomizing a list. The commented code is included below. This is actually pretty much exactly what you describe as your "second idea", but hopefully the comments will help clarify what's going on with it:

Code:

ShufList
\<<
  @ explode the list onto stack and save the size (sz)
  OBJ\-> \-> sz

  \<<
    @ loop: for list item positions 1 to (sz-1), choose a
    @ random item from the remaining candidates and move it
    @ to the target position

    @ note: stack positions (sz...1) are numbered inversely to
    @ list positions (1...sz)

    @ x represents the current target position
    sz 2 FOR x

      @ pick a random item position from the remaining pool
      x RAND * CEIL

      @ move the chosen item to stack level 1
      ROLL

      @ move the chosen item to the current target position
      x ROLLD

    @ update target to the next position
    -1 STEP

    @ implode the resulting list data
    sz \->LIST
  \>>
\>>

The code is reasonably compact and fast. Performance is directly proportional to list size, and on my 50g can handle a list of 100 items in about 1 second. I'm sure someone else here can make a smaller/faster version, but this one has worked well for me.

[pier4r]

Thanks for sharing (I'll have to check more the article from J.H.), yes it is pretty similar to what I thought as second idea. Would be interesting is someone has some other approaches (apart from ROLL ROLLD or even those but with subtle optimizations).

Actually with my shuffle I'm fine, the only point I started to be concerned "how many shuffles do I have to do to have a random order compared to the one from the start?"

Something like this https://www.youtube.com/watch?v=AxJubaijQbI (forgive me for the video, but it is interesting, check at least the first 45 seconds, there are also links to papers in the description)

[pier4r]

So far a version of the article that I want to finish with the result is here. Be warned that my English is pretty poor and I have still to proofread the entire article at least once more and fix some parts, but the idea is there.

In the meanwhile, since proofreading for me is quite costly in terms of time, the 50g is computing some more results.

Of course, the grammar/math/userRPL/50g Police is welcomed.