Code optimising help

[DDRM]

Hi Kendall and Richard,

Kendall, you'll note that Richard's testing program uses 0 - 1439 (24 * 60 -1), consistent with the "midnight is tomorrow" convention. I'm sure it didn't slip Richard's mind!

Richard, I don't have time to play with this this morning, but it occurs to me that it should be possible to use a binary search to find S, which should reduce the worst case loop from 1440 to 11? On the downside, the loop would then have to include the multiplications in the encoding formula, which may be sufficiently slower than the integer adds that it counteracts the gain.

I suspect there may be some trick either using either a "sum of consecutive integers" approach, or by taking log base 1440 of T, but I haven't worked on it yet...

Best wishes,

D

[Hated Moron]

The fact that the incorrect answer returned by having 1440 as the second parameter slipped your notice indicates to me that the full range is unlikely.

Nothing "slipped my notice"; having 1440 as the second parameter is impossible because at the User Interface the times are, of course, entered in hh:mm format so the allowed range is 00:00 to 23:59. To achieve a parameter of 1440 it would be necessary to enter a day/date as well as a time.

It's always the same with you. You misunderstand or misconstrue something, but it's always somebody else's fault - usually mine. You could so easily have said "I notice that an invalid result is returned when passing 1440 as the second parameter, is that deliberate?" which is polite and would have prompted an equally polite explanation in return. But no, you say that the answer is "incorrect" and that it "slipped my notice", which is insulting and untrue.

I agreed to re-join this forum on condition that I was given a veto over your posts, and that was accepted by the administrator. But that seems to have been forgotten, because I was given no opportunity to reject your post and request that it be rewritten in a more conciliatory tone.

[DDRM]

Hi Richard,

To be fair to me, the agreement was that Kendall's posts would be moderated, but you or me. In this case I saw it first, considered it, but decided to allow it, but posted a "correction", to point out that actually our algorithm was fine, so if the blame falls anywhere, it is on my judgement of what was acceptable.

As a general point, please can I encourage EVERYONE to try to take a moderate, constructive tone in their posts.

Best wishes,

D

[nvingo]

More information is required

Sorry, I thought it was obvious from the fact that I already listed the encoding function and it is just the decoding function that I am looking for help on. But, yes, both start and finish times must be in the range 0-1439 and the finish time must be greater-than-or-equal-to the start time. I am not allowing for the times to 'span' midnight because if they did encoding them into a 20-bit number would be impossible!

Thank you for clarifying. It was implicit but I thought it worthwhile checking.

However, although my programming skills are at best rusty, I thought to see what results were comparing the input values with the decoded output.
Test routine (plus cut/paste of the FN and PROC from post#1):

Code: Select all

      REM tester

      MODE0
      VDU14
      start%=0

      REPEAT
        finish%=0
        REPEAT
          coded%=FNencodetimes(start%,finish%)
          IF coded%<>coded%AND&0FFFFF PRINT "Too many bits >",~coded%,start%,finish%
          PROCdecodetimes(coded%,checkstart%,checkfinish%)
          IF checkstart%<>start% PRINT "Start mismatch >",start%,checkstart%
          IF checkfinish%<>finish% PRINT "Finish mismatch >",finish%,checkfinish%

          finish% += 1
        UNTIL start%+finish%>1439
        start% += 1
      UNTIL start%>1439
      PRINT "all done!"
      STOP

I guess I'm calling the PROC incorrectly, as the program reports a mismatch between the start and the decoded encoded start, and the finish and decoded encoded finish for each submitted pair.
This is too weird; even after replacing the IF..GOTO with REPEAT UNTIL, the input and output still don't match.

[Hated Moron]

To be fair to me, the agreement was that Kendall's posts would be moderated, by you or me.

I see, in that case I misunderstood the agreement. I am not prepared to remain a member of this forum on that basis, please delete my membership forthwith. Thanks.

[Flatlander]

(I thought I posted this at groups.io but it’s not showing.)

Apologies if this is wrong, or I have something off-by-one etc.

Simplifying, by using 10 instead of 1440 etc. and setting the duration to 0, a pattern of triangle numbers can be seen in the output of the encode function. More clearly by flipping it ‘upside down’:
output = ((10*11) DIV 2 ) - output

So in the decode function:
T% = ( (1440*1441) DIV 2) - T%
REM T% now consists of a triangle number plus a duration of zero or more.
Pseudo code: LET tri be the nth triangle number, the largest triangle number <= T%
S% = 1440-n
duration = tri - T%: REM minus, because T% is ‘upside down’
F% = S% + duration

A Google search shows that finding the highest triangle number < a certain number should be straightforward. (Needed here is <=.)

[KenDown]

It seems to me that those who go on about the number of bits required for numbers of the magnitude given are rather missing the point. They (as I did) are envisaging a completely new method of encoding. Richard has already demonstrated that his formula can encode the two numbers in a way that can be reliably decoded while remaining within his limit of 20 bits.

However it also seems to me that the "brute force" method he uses is the only one possible, because he is basically asking us to solve a formula of the type A+B=C where both A and B are unknowns. If there was some simple mathematical relationship between A and B - for example, 2A+B=C - we might have a chance, but in fact the formula for the first number is, to my simple mind at least, horribly complex.

fn(S%)+F%=T% where fn(S%) stands for S%*(2881-S%)DIV2-S%

Swapping things around would (I think) give you F%=T%-fn(S%) but the value of S% is still unknown.

There is something curious about this function, which can be illustrated with this code snippet.

Code: Select all

      x%=0
      FORS%=0TO1439
        T%=S%*(2881-S%)DIV2-S%
        PRINTS%"   "T%"  "T%-x%
        x%=T%
        g%=GET
      NEXT

In words, as you increase the value of S% by 1, the difference between the result and the previous result is always 1. Whether that, in conjunction with the fact that F% must always be greater than S%, gives anyone with a mathematical bent an "Aha!" moment, I couldn't say.

[Hated Moron]

The fact that the incorrect answer returned by having 1440 as the second parameter slipped your notice...

As I said, nothing "slipped my notice"; 1440 is impossible as the second parameter because I am handling only times, not dates, so the maximum possible range is 00:00 - 23:59 or 0 - 1439 in minutes. Are you going to apologise for that unjustified assertion or not?

[KenDown]

Certainly, I'm glad to apologise. It was not my intention to upset you.