Code optimising help

[Hated Moron]

I have two functions, one which takes a pair of times (a start time and a finish time, expressed in minutes) and encodes them as a single 20-bit integer:

Code: Select all

      DEF FNencodetimes(S%, F%) = (S% * (2881 - S%)) DIV 2 + F% - S%

and one which performs the reverse operation, taking a 20-bit integer and decoding it to a pair of times:

Code: Select all

      DEF PROCdecodetimes(T%, RETURN S%, RETURN F%)
      LOCAL I%, N%
      I% = 1440
      S% = 0
      WHILE (N% + I%) <= T%
        N% += I%
        I% -= 1
        S% += 1
      ENDWHILE
      F% = S% + T% - N%
      ENDPROC

You can see that whilst the first function is a simple expression, the second involves an iterative approach. I feel that it should be possible to code the second function as a relatively simple expression too, after all it's only a mathematical operation. But my cognitive decline has impaired my ability to write and understand code to such an extent that I just can't see how to do it.

I would be very grateful if somebody can devise a simplification. I should perhaps add that I know that converting to and from a 21-bit integer would be trivial, but in my application it has to be twenty bits.

[KenDown]

I'm afraid that I can't follow the logic of your first function at all, though if it works, great. However if you want twenty bits, it seems to me that you can achieve your end by considering the two numbers as two lots of 10-bits - and that means raising one of them by 9, ie. x%<<9. No doubt there is much wrong with my idea, but this is how I would do it.

Code: Select all

      T%=FNencodetimes(10,20)
      PRINTT%
      PROCdecodetimes(T%,S%,F%)
      PRINTS%" "F%
      END
      :
      DEFFNencodetimes(S%,F%)
      =((F%<<9)+S%)
      :
      DEFPROCdecodetimes(T%,RETURN S%,RETURN F%)
      S%=T%AND1023
      F%=T%>>9
      ENDPROC

Is there a binary equivalent of the tilde for hexadecimal?

[Hated Moron]

I'm afraid that I can't follow the logic of your first function at all, though if it works, great.

Yes, it works fine as you can easily ascertain yourself. If you can see a way of simplifying it then of course that would be useful too, but it's the (much more complicated and slower) second function that I am looking for help with.

However if you want twenty bits, it seems to me that you can achieve your end by considering the two numbers as two lots of 10-bits

There are 24 * 60 = 1440 minutes in a day, how do you propose to encode that as 10 bits? It's impossible!

I said that it was trivial to encode the two times in 21 bits, which is what happens if you use the technique that you propose, but I need to encode them into 20 bits (which my first function achieves, it's the decoding that is messy).

Although I am grateful for all offers of help, if you don't understand the question I'm afraid you are unlikely to be able to contribute.

[Hated Moron]

I'm afraid that I can't follow the logic of your first function at all

In case anybody else is unsure of the first (encoding) function here's a test program to confirm that it works. If it ever generated a number needing more than 20 bits the program would fail with a 'Bad subscript' error; if it ever generated the same encoded value from different pairs of times, it would report 'Collision!". Since it does neither you can see that it is a successful encoding of a start/finish time pair into 20 bits.

Code: Select all

      DIM e&(2^20-1)
      FOR start% = 0 TO 24*60-1
        FOR finish% = start% TO 24*60-1
          E% = FNencodetimes(start%, finish%)
          IF e&(E%) THEN PRINT "Collision!" : STOP
          e&(E%) = 1
        NEXT
      NEXT start%
      PRINT "Completed successfully"
      END

      DEF FNencodetimes(S%, F%) = (S% * (2881 - S%)) DIV 2 + F% - S%

[nvingo]

which takes a pair of times (a start time and a finish time, expressed in minutes)

More information is required; what is the valid range of each time (0-1439 ?) and can the finish time be earlier (aka the next day)? If the duration (F%-S%) is limited - to less than 12 hours - that can be used to advantage. Can the granularity be changed, eg. every two minutes or every five minutes, or does it have to be minute-accurate?
As a starting point, without encoding 1440 values needs 11 bits; two numbers needs 22 bits.
Combine the numbers with *, and separate them with DIV and MOD, you still need 21 bits.
Limit the start time to AM, or the duration to 12 hours (either is 720 minutes), and 20 bits suffice.
If it's always the same day, the start time + duration, never exceeds 1440 minutes, but if either can exceed 1023 minutes I can't think how to flag which it is without extra bits; that does lead to if the start time is always less than 416 minutes (06:55) or the duration is then 20 bits can suffice with that knowledge.

[DDRM]

Hi Richard,

Quick statement of the problem, as I see it:

1) I'm assuming that start is always less than finish, and that both occur on the same day, with no preceding days to worry about - so both are positive, and at most 1440.

2) Effectively we encode the start time, together with the duration (F - S), since (start + duration) is also bounded by 1440.

2) As I understand it, it is possible to pack two (potentially) 11 bit numbers into 20 bits because we know that at least one of them needs at most 9 bits (edit: if the other is 11 bits: both could be 10 bits), since if one of them exceeds 1023 then the other must be less than 512. The problem arises because we don't know which values (if either) are big!

I can make a trivial improvement to your (already fast and efficient!) encoding function by taking the final "-S%" inside the first part of the expression:

T = (2879 - S%)*S%/2 +F%

I note that (2879 - S%)*S% is always even, since one of the elements must be even (and the other odd), so division by two will always give an integer result. The choice between /, DIV, and >> is thus presumably one of speed?

This expression is obviously a quadratic, but with two variables in it, so not susceptible to closed-form solution... No more brilliant ideas, but I'll think about it.

Best wishes,

D

[Hated Moron]

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!

[Hated Moron]

As I understand it, it is possible to pack two (potentially) 11 bit numbers into 20 bits because we know that at least one of them needs at most 9 bits (edit: if the other is 11 bits: both could be 10 bits), since if one of them exceeds 1023 then the other must be less than 512. The problem arises because we don't know which values (if either) are big!

You've rather confused me because you are stating the requirements for the encoding function which I have already created and tested! There is no "problem" in the sense in which you describe it, because I have already solved it (it was quite straightforward, hence why I was able to manage it without help, even in my current condition).

I can make a trivial improvement to your (already fast and efficient!) encoding function by taking the final "-S%" inside the first part of the expression:

T = (2879 - S%)*S%/2 +F%

OK, noted, thanks.

The choice between /, DIV, and >> is thus presumably one of speed?

No active "choice" was made, I just wanted an integer division and that is what DIV does. Using / would mean the two integer values first being converted to floating-point, a floating=point division then being performed, and finally the quotient being truncated and converted to an integer.

This expression is obviously a quadratic

There speaks a mathematician - nothing about it is "obvious" to me at all! But if what you are saying is that it is therefore insoluble other than by iterative means then that in itself is a valuable (if annoying) conclusion. Might there at least be some way of reducing the number of iterative steps required?

I am sorry that my post has obviously caused a great deal of annoyance - if not anger. Clearly I should never have asked the question in the first place; please delete the entire thread. I am unfortunately not able to post to the discussion group, but I may try the Facebook group because that has (so far) remained friendly.

[DDRM]

Hi Richard,

Certainly no distress or annoyance here - it's an interesting problem.

Yes, my statement of the problem largely relates to the encoding, which is, as you say, solved. I provided it to ensure that I understood the parameters of the problem (and partly in response to nvingo's request for further detail). It might be that an alternative encoding approach would facilitate a simpler decoding process, so I thought it worthwhile to think about both sides of the problem. I confess it still isn't obvious to me exactly how/why the encoding, or indeed decoding, work(s).

My comments about quadratics certainly don't exclude a closed solution - just that the standard solution "(-b +/- SQR(b^2-4ac))/2a" can't be used, since we don't know c (which here is F). I'll have a think about it, and get back to you if I think of anything clever, but I wouldn't hold your breath - despite your comment, I'm no mathematician!

Best wishes,

D

[KenDown]

I agree. Neither annoyance nor anger.

I notice that, using Richard's function and procedure, you cannot have 1440 minutes. t%=FNencodetimes(0,1440) decodes to 1,1 whereas t%=FNencodetimes(0,1439) decodes correctly to 0,1439. You would have to change I%=1440 to I%=1441 to get the correct answer.

I agree with someone else who asked what the likely parameters are. Is the full range of 0-1440 ever likely? Or are much smaller periods of time invariable? 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.