Shop OBEX P1 Docs P2 Docs Learn Events
Function Calculation — Parallax Forums

Function Calculation

KyeKye Posts: 2,200
edited 2015-06-27 17:26 in Propeller 1
Anyone know how to find the exact function for this sequence?

0 1
1 2
2 2
3 3
4 3
5 3
6 4
7 4
8 4
9 4
10 5
11 5
12 5
13 5
14 5
15 6
16 6
17 6
18 6
19 6
20 6
21 7
22 7
23 7
24 7
25 7
26 7
27 7
28 8
29 8
30 8
31 8
32 8
33 8
34 8
35 8
36 9
37 9
38 9
39 9
40 9
41 9
42 9
43 9
44 9
45 10
46 10
47 10
48 10
49 10
50 10
51 10
52 10
53 10
54 10

I've found the function: floor(sqrt(x*1.799))+1 to be a close fit. However, I don't think that's quite right. The sequence is easy enough to see... (y repeat an incrementing number of times) but, I can't seem to figure out the exact equation.

Comments

  • trangertranger Posts: 179
    edited 2015-06-27 10:11
    There is a solution for x starting at 1 rather than zero. y = CEILING((SQRT(1+8*x) -1) / 2)

    Not sure if that is helpful or not....

    Doh! this should work: y =Ceiling( (SQRT(1+8 * ( x +1)) -1) / 2 )

    -Russ
  • Beau SchwabeBeau Schwabe Posts: 6,566
    edited 2015-06-27 10:22
    Kye,

    You can do this with integer math...

    Y = 1+((N/1)/(N/1))+((N/3)/(N/3))+((N/6)/(N/6))+((N/10)/(N/10))+((N/15)/(N/15))+((N/21)/(N/21))+((N/28)/(N/28))+((N/36)/(N/36))+((N/45)/(N/45))
  • Ding-BattyDing-Batty Posts: 302
    edited 2015-06-27 10:23
    This should also work, for x => 0

    y := Floor((sqrt(1+8x)+1)/2)
  • KyeKye Posts: 2,200
    edited 2015-06-27 11:00
    y := Floor((sqrt(1+8x)+1)/2)

    Is perfect!!! How did you guys figure that out? Also, there's another part I need help with:

    x, y
    0: return 0; (count down from 1)
    1: return 1; (count down from 2)
    2: return 0; (count down from 2)
    3: return 2; (count down from 3)
    4: return 1; (count down from 3)
    5: return 0; (count down from 3)
    6: return 3; (count down from 4)
    7: return 2; (count down from 4)
    8: return 1; (count down from 4)
    9: return 0; (count down from 4)
    10: return 4; (count down from 5)
    11: return 3; (count down from 5)
    12: return 2; (count down from 5)
    13: return 1; (count down from 5)
    14: return 0; (count down from 5)
    15: return 5; (count down from 6)
    16: return 4; (count down from 6)
    17: return 3; (count down from 6)
    18: return 2; (count down from 6)
    19: return 1; (count down from 6)
    20: return 0; (count down from 6)
    21: return 6; (count down from 7)
    22: return 5; (count down from 7)
    23: return 4; (count down from 7)
    24: return 3; (count down from 7)
    25: return 2; (count down from 7)
    26: return 1; (count down from 7)
    27: return 0; (count down from 7)
    28: return 7; (count down from 8)
    29: return 6; (count down from 8)
    30: return 5; (count down from 8)
    31: return 4; (count down from 8)
    32: return 3; (count down from 8)
    33: return 2; (count down from 8)
    34: return 1; (count down from 8)
    35: return 0; (count down from 8)
    36: return 8; (count down from 9)
    37: return 7; (count down from 9)
    38: return 6; (count down from 9)
    39: return 5; (count down from 9)
    40: return 4; (count down from 9)
    41: return 3; (count down from 9)
    42: return 2; (count down from 9)
    43: return 1; (count down from 9)
    44: return 0; (count down from 9)
    45: return 9; (count down from 10)
    46: return 8; (count down from 10)
    47: return 7; (count down from 10)
    48: return 6; (count down from 10)
    49: return 5; (count down from 10)
    50: return 4; (count down from 10)
    51: return 3; (count down from 10)
    52: return 2; (count down from 10)
    53: return 1; (count down from 10)
    54: return 0; (count down from 10)
    etc.

    Basically, I'm counting down from "y := Floor((sqrt(1+8x)+1)/2)" using x. I think the solution involves some modular arithmetic, but, I don't know.
  • Beau SchwabeBeau Schwabe Posts: 6,566
    edited 2015-06-27 11:08
    Kye,

    In your second request ... calculate Y first as before ...

    y := Floor((sqrt(1+8x)+1)/2)

    ... Then use Y as a Modulus function against X to get the return value you are requestng
  • KyeKye Posts: 2,200
    edited 2015-06-27 11:58
    That doesn't wok.

    The answer is more complex than:

    y := Floor((sqrt(1+8x)+1)/2)

    val := x % y

    In the lookup table above, using such a function fails after the first values. Adding a constant offset too x is not a solution either. I think some kind of offset based on y needs to be added to x before the mod.
  • Beau SchwabeBeau Schwabe Posts: 6,566
    edited 2015-06-27 13:48
    Kye,

    Still can be solved with integer math... here is a Basic Stamp II program that shows the result.

    Where Z is the input variable

    Y is the first requested Output
    Z is the second requested Output
    ' {$STAMP BS2}
' {$PBASIC 2.5}


X VAR Byte
Y VAR Byte
Z VAR Byte


FOR X = 0 TO 54

    Y = ((X/1)/(X/1))+((X/3)/(X/3))+((X/6)/(X/6))+((X/10)/(X/10))+((X/15)/(X/15))
    Y = Y +((X/21)/(X/21))+((X/28)/(X/28))+((X/36)/(X/36))+((X/45)/(X/45)) + 1

    Z = (Y-((X + ((1-(Y & 1))* Y>>1)) // Y))-1

    DEBUG DEC X,TAB, DEC Y,TAB,TAB, DEC Z,CR
NEXT
  • trangertranger Posts: 179
    edited 2015-06-27 15:37
    Kye wrote: »

    How did you guys figure that out?

    I can try to explain how I did it.

    Think about the series 1 + 2 + 3 + 4 etc... In your y column the number of 1's is 1 and 2's is 2 and 3's is 3 and so on. So the total number of terms in the Y column for a given number is the sum of that series. The number of terms is also the X column (except shifted by one).

    For example, the number of terms for Y =4 is 1 + 2 + 3 + 4. Thanks to Wikipedia, one can find the sum of such a series as n(n + 1) / 2. That's great if you want to get from y to x. For your case, you can use the quadratic equation to solve x = y ( y + 1) / 2 for y. You'll get y = ( sqrt (1 + 8x) - 1 )/ 2.

    Once you get that far, the rest is probably more obvious. You only get integer numbers for y if x is at the end of a series of repeating numbers. Screwing around with floors and ceilings addresses that. I subbed in x-1 for x to shift everything to account for starting at zero.
  • KyeKye Posts: 2,200
    edited 2015-06-27 16:48
    @ Beau Schwabe - Thanks!

    This code is not actually for running on the propeller/basic stamp. I asked the above questions because I was trying to implement a parallel bitonic merge sorter in hardware. See this random homework assignment for details: http://web.mst.edu/~ercal/387/P3/pr-proj-3.pdf.

    I was trying to implement the algorithm using generate statements in system verilog and I was running into a bunch of issues that prevents me from just doing:
    int; l = 0;
for(int i = 1; i <= D; i++) begin
  for(int j = (i-1); j >= 0; j--) begin
    for(int k = 0; k < (1 << D); k++) begin
    end
    l++;
  end
end

    So, I was trying to turn the loop inside out by just having on variable increment and compute the rest of the loop from that.

    ...

    However, the verilog synthesizer refuses to do anything once it finds any $floor or $sqrt functions and just quits on that. So, with even the above, I had to figure out another way.

    I did manage to get the code working without having to hard code anything however, the solution was not to use any generate statements and just to put everything into a always block where you can use complex variable assignments.

    ---

    @tranger - I see. Really good math skill there.
  • Beau SchwabeBeau Schwabe Posts: 6,566
    edited 2015-06-27 17:26
    Ok, so what ... if it can run on a Basic Stamp it should be able to run on anything ... it's just integer math
Sign In or Register to comment.