Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.


Messages - Xeda112358

Pages: [1] 2 3 ... 316
1
Math and Science / Re: A faster Newton's Method Square Root
« on: Yesterday at 10:11:37 pm »
I fixed the link, thanks :)

For TI Floats, the first byte is actually used to indicate variable type (lower 5 bits), and for floats, TI uses the upper bit to indicate sign. The next byte is used for the exponent, and then 7 bytes for the 14 digits, for a total of 9 bytes.

TI also uses extra precision for some intermediate operations, so sometimes the floats are actually larger (which is why the OPx spots in RAM are 11 bytes instead of 9).TI uses BCD because numbers are entered in base 10, and they want that to be handled "exactly," especially for financial usage. (BCD has the same rounding issues as binary floats, it just happens at different places).

I'm personally not a fan of BCD, as it is wasteful and slow, and binary floats can do the job. The only advantage with BCD floats is that with financial math, you don't have to be careful with comparisons.

As for the speed of that 32-bit square root routine, remember that it is fully unrolled, and relies on a fully unrolled 16-bit square root for a grand total of about 270 bytes. Also note: the routine I linked to is an integer square root routine. The floating-point routine is probably closer to 2000cc as it needs an extra 8 bits of precision in the result and some special handling for the exponent and "special values." That said, yes, there are some advantages to the floating-point format, especially with division and square roots.

EDIT: Actually, the original link to sqrtHLIX doesn't even use this technique, so I updated it to point to sqrt32 which does use this technique, and expects the upper two bits of the input to be non-zero (which is guaranteed with these binary floats)

2
Math and Science / Re: A faster Newton's Method Square Root
« on: Yesterday at 07:30:26 pm »
I never followed up with this! A little while after, I refined this significantly and then a year or two ago, I implemented it in my z80float z80float library (link is directly to sqrtHLIX sqrt32) and that's how I made square roots faster than multiplication.

Today I was excited to learn that this is how GMP does it, it just looks scarier there because they are optimizing the notation to make it easy to implement in code without necessarily understanding how it works (which is cool, they present the pseudocode in a very easy-to-digest manner). But that's not what I'm here for, I'm here to show how it works!

Here is the TL;DR if you don't want to go through the derivation:
##
\begin{array}{rcl}
x_{0} & \approx & \sqrt{c} \\
a_{0} &=& c - x_{0}^{2} \\
q_{n} + \frac{r_{n}}{2x_{n}} &=& \frac{a_{n}}{2x_{n}} \\
x_{n+1} &=& x_{n} + q_{n} \\
a_{n+1} &=& r_{n} - q_{n}^{2} \\
\end{array}
##

(The third line means "divide ##\frac{a_{n}}{2x_{n}}##, but truncate at some precision to get the quotient and the remainder")



Let's start. I like the "Babylonian Method" where you start with a guess ##x_{0}## as an approximation to the square root of ##c##, then you run this iteration a few times until you have the precision you want:
##
\begin{array}{l}
x_{n+1} &=& \frac{\left(x_{n}+\frac{c}{x_{n}}\right)}{2}
\end{array}
##

All you are doing is averaging the guess, with ##c## divided by that guess. If your guess was an overestimate, ##\frac{c}{x_{n}}## is going to be an underestimate, so their average will be closer to the actual answer.


And that's just a simplification of the Newton Iteration:
##
\begin{array}{l}
x_{n+1} &=& x_{n} + \frac{c-x_{n}^{2}}{2x_{n}}
\end{array}
##


We are going to build off of the Newton Iteration, but make it a little more complicated by turning ##c-x_{n}^{2}## into it's own recurrence:
##
\begin{array}{l}
a_{n} &=& c-x_{n}^{2} \\
x_{n+1} &=& x_{n} + \frac{a_{n}}{2x_{n}}
\end{array}
##


And actually, in practice we are going to truncate that division so that ##q_{n} + \frac{r_{n}}{2x_{n}} = \frac{a_{n}}{2x_{n}}## where ##q_{n}## is the (truncated) quotient, and ##r_{n}## is whatever the remainder was after dividing by ##2x_{n}##. So what we'd really be doing is:
##
\begin{array}{rcl}
a_{n} &=& c-x_{n}^{2} \\
q_{n} + \frac{r_{n}}{2x_{n}} &=& \frac{a_{n}}{2x_{n}} \\
x_{n+1} &=& x_{n} + q_{n}
\end{array}
##


Now that everything is more complicated, let's take a look at what happens to ##a_{n+1}##:
##
\begin{array}{l}
a_{n+1} &=& c-x_{n+1}^{2} \\
&=& c-(x_{n} + q_{n})^{2} \\
&=& c-(x_{n}^{2} + 2x_{n}q_{n} + q_{n}^{2}) \\
&=& c - x_{n}^{2} - 2x_{n}q_{n} - q_{n}^{2} \\
&=& a_{n} - 2x_{n}q_{n} - q_{n}^{2} \\
\end{array}
##


Already, we have an optimization. Those two multiplications are half the precision of a full ##x_{n+1}^{2}## if you do it right, and that is strictly faster. But we're not done! Remember that division? Let's re-write it:
##
\begin{array}{rcl}
q_{n} + \frac{r_{n}}{2x_{n}} &=& \frac{a_{n}}{2x_{n}} \\
2x_{n}q_{n} + r_{n} &=& a_{n} \\
r_{n} &=& a_{n} - 2x_{n}q_{n} \\
\end{array}
##


Well ain't that awfully convenient? Let's rewrite our ##a_{n+1}## recurrence:
##
\begin{array}{l}
a_{n+1} &=& a_{n} - 2x_{n}q_{n} - q_{n}^{2} \\
&=& r_{n} - q_{n}^{2} \\
\end{array}
##


So now we've significantly improved that step by replacing the squaring operation with one at half the precision! Let's look at the recurrence relations now:
##
\begin{array}{rcl}
q_{n} + \frac{r_{n}}{2x_{n}} &=& \frac{a_{n}}{2x_{n}} \\
x_{n+1} &=& x_{n} + q_{n} \\
a_{n+1} &=& r_{n} - q_{n}^{2} \\
\end{array}
##


Neat!



Now let's retry our example of finding the square-root of 21:
##
\begin{array}{rcl}
x_{0} & \approx & \sqrt{c} \\
&=& 4\\
a_{0} &=& c - x_{0}^{2} \\
&=& 21-16 \\
&=& 5 \\
q_{0} + \frac{r_{0}}{2x_{0}} &=& \frac{a_{0}}{2x_{0}} \\
&=&\frac{5}{8} \\
&=&.5 + \frac{1}{8} \\
x_{1} &=& x_{0} + q_{0} \\
&=& 4.5 \\
a_{1} &=& r_{0} - q_{0}^{2} \\
&=& 1 - .5^{2} \\
&=& .75 \\

q_{1} + \frac{r_{1}}{2x_{1}} &=& \frac{a_{1}}{2x_{1}} \\
&=&\frac{.75}{9} \\
&=&.083 + \frac{.003}{9} \\
x_{2} &=& x_{1} + q_{1} \\
&=& 4.583 \\
a_{2} &=& r_{1} - q_{1}^{2} \\
&=& .003 - .083^{2} \\
&=& -.003889 \\

q_{2} + \frac{r_{2}}{2x_{2}} &=& \frac{a_{2}}{2x_{2}} \\
&=&\frac{-.003889}{9.166} \\
&=&-.0004243 + \frac{.0000001338}{9.166} \\
x_{3} &=& x_{2} + q_{2} \\
&=& 4.5825757 \\

\end{array}
##


EDIT: updates z80float link to point to the routine that actually implements this

3
Introduce Yourself! / Re: Hello!
« on: June 28, 2022, 07:46:41 pm »
\o/ Welcome to Omni! Have some !peanuts :D

4
The Axe Parser Project / Re: Handling multiple inputs at once
« on: June 28, 2022, 04:20:56 pm »
You were on the right track-- "getKey" on its own returns a single keypress, but you can also use "getKey(n)" to check if key "n" is pressed (it returns 0 for not pressed, 1 for pressed).

So if you want to check for both Enter and the Down arrow, simultaneously:
Code: [Select]
If getKey(9)
//Enter is pressed
End

If getKey(1)
//Down is pressed
End

You can also do some useful arithmetic, like if you have (X,Y) coordinates, you might want:
Code: [Select]
X+getKey(3)-getKey(2)→X
Y+getKey(1)-getKey(4)→Y
And that has a bonus of letting the user press multiple arrow keys simultaneously :)

Hopefully that helps!

EDIT: Also, welcome to Omninaga, you should Introduce Yourself!

5
TI Calculators / Re: Need Help With a Possible Bricked TI-84+CSE
« on: May 28, 2022, 05:24:43 pm »
You'll need to start the process of sending the OS to your calc before you press ON. EDIT: In fact just don't press ON unless you are trying to turn off your calc.

Have you tried TiLP instead of TI Connect? Warning: I believe on Windows you can only have one installed at a time, they have drivers that interfere with each other.

Are you sure you have the right OS file, and not one for the monochrome calcs or CE? (CE is very different from CSE)

6
ASM / Re: Sine Approximation [Z80]
« on: February 03, 2022, 09:08:55 pm »
Necropost: this came up elsewhere and I made a python version if anybody is interested. I think it could be implemented really well with logic gates!
https://gist.github.com/Zeda/98aab98fd32a231b878772a435ffb306

Code: [Select]
#!/usr/bin/python3

# This is ported from:
#    https://www.omnimaga.org/asm-language/sine-approximation-(z80)/
# (Xeda112358  a.k.a.  Zeda  a.k.a.  ZedaZ80)
#

from math import sin

def sineb(x):
    """Approximates 128*sin(x*2*pi/256)"""

    a1 = int(x)
    a0 = a1 << 1
    a2 = a1 >> 1

    # iteration 1
    if a1 & 64:
        l = ~a0 & 127
    else:
        l =  a0 & 127

    # iteration 2
    if a1 & 32:
        l += ~a1 & 31
    else:
        l +=  a1 & 31

    # iteration 3
    if a1 & 16:
        l += ~a2 & 7
    else:
        l +=  a2 & 7

    # check if it needs to be negated
    if a1 & 128:
        return -l
    else:
        return l

# Plot a graph of the approximation vs the actual
for x in range(0, 256, 2):
    y = sineb(x)
    z = int(sin(x*3.1415926535/128)*128)

    # translate and scale for "graphing"
    y += 128
    z += 128
    y >>= 1
    z >>= 1

    # "graph"
    #    X - Approximation
    #    O - Actual
    #    8 - used when the graphs overlap
    if y == z:
        print(" "*y + "8")
    elif y > z:
        print(" "*z + "X" + " "*(y-z-1) + "O")
    else:
        print(" "*y + "O" + " "*(z-y-1) + "X")

7
Axe / Re: Looping Through an Array in Axe
« on: December 15, 2021, 08:13:45 am »
I'm thinking it might be an order-of-operations issue since Axe obeys parentheses, but is otherwise left-to-right instead of PEMDAS.

Instead of this:
Code: [Select]
      If (RoomX≥XMin and RoomX≤XMax) and (RoomY≥YMin and RoomY≤YMax)
        0→R
        GetRoomStart()
      End
      !If (RoomX≥XMin and RoomX≤XMax) and (RoomY≥YMin and RoomY≤YMax)
        R++
      End
Try:
Code: [Select]
      If (RoomX≥XMin) and (RoomX≤XMax) and (RoomY≥YMin) and (RoomY≤YMax)
        0→R
        GetRoomStart()
      Else
        R++
      End

8
Axe / Re: Axe Loops not Working as Expected
« on: December 09, 2021, 07:39:39 pm »
The code is difficult to follow, but it looks like you are mixing 0-indexing and 1-indexing.
You loop J from 1 to Rooms, but then you are checking if J>0 in the same loop (which is always true).

J+(J*((J>0)*4))-4→Y
Simplifies to:
J+(J*(1*4))-4→Y
J+(J*4)-4→Y
J*5-4→Y

Maybe there is something there?

9
That is amazing :0

10
TI Z80 / Re: Elimination RPG: Early Release Build!!
« on: November 25, 2021, 02:01:27 pm »
Could it be that I used WabbitSign?  Should I use something else to sign the app?
I haven't used wabbitsign in a long time and I'm not sure if that is the issue. I generally use spasm and I've got it configured to automatically sign apps.

I know Wabbitemu is very generous with loading apps (it bypasses the calc's security which is great for streamlining development, but it hides signing issues).

I'm not much help with this stuff these ays XD .__.

11
TI Z80 / Re: Elimination RPG: Early Release Build!!
« on: November 25, 2021, 07:58:34 am »
I cannot send the 8xk file to my 84+. I get an error saying the application file is broken and to redownload it again, and if it doesn't work, to contact TI for help. D:
Out of curiosity, can you send it to an emulator?

12
TI Z80 / Re: Alien Breed 5 Episode III: Impact
« on: November 13, 2021, 08:10:25 am »
Holy heck that looks so good :O

13
TI Z80 / Re: Elimination: An RPG inspired by Earthbound / Pokemon
« on: November 07, 2021, 06:35:35 am »
Oh yeah, that definitely works :0

14
TI Z80 / Re: Elimination: An RPG inspired by Earthbound / Pokemon
« on: October 23, 2021, 04:03:12 pm »
Awww yiss, that looks pretty cool!
I definitely like the monochrome graphics (I also find that grayscale is just too rough to look at on actual hardware and with moving images).

15
ASM / Re: eZ80 Optimized Routines
« on: October 11, 2021, 12:32:17 pm »
Oh, fantastic! Good catch!

Pages: [1] 2 3 ... 316