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 ... 317
1
Oof, yeah, I heard about the Freenom issues .__. Hopefully your new one works better!

And about the Superstar Hero OST-- wow o_o

2
Axe / Re: Axe Q&A
« on: July 21, 2022, 03:47:37 pm »
Could you give us some code to look at? Pt-Change( should definitely work

3
Axe / Re: A* Star and Min Heap Help
« on: July 10, 2022, 03:28:33 pm »
So this isn't exactly what you need, but here is an example program I worked on that implements pushing to and popping from a heap. In this example, I push 30 random values and then pop them off, storing the scores to an array at oMINHEAP+128, resulting in a sorted list.

You'll want to change how the "score" is calculated, as well as the 2-byte "value" associated with it in Lbl PUSH. Otherwise, you should be able to PUSH() and POP() as expected :)

Code: [Select]
.HEAP
L1+18->->^^oHEAPSIZE
L1+20->->^^oPARENT
L1+22->->^^oLCHILD
L1+22->->^^oCHILD  //Alias
L1+24->->^^oRCHILD
L1+26->->^^oSCORE
L1+28->->^^oVALUE
L1+30->->^^oMINHEAP

0->HEAPSIZE

For(30)
    PUSH(rand^16,rand^16)
End

^^oMINHEAP+127->Z
While HEAPSIZE
    POP()
    SCORE->{Z++}
End
Return

Lbl PUSH
    HEAPSIZE*3+^^oMINHEAP->A
    [r1]+[r2]->{A}
    [r1]->{A++}
    [r2]->{A++}
    HEAPSIZE++
    PROPUP(HEAPSIZE-1)
Return

Lbl POP
    Return!If HEAPSIZE
    //We'll return the root node
    {^^oMINHEAP}->SCORE
    {^^oMINHEAP+1}^^r->VALUE
    HEAPSIZE--
    Return!If HEAPSIZE

    // Backup the parent's data
    HEAPSIZE*3->P
    {^^oMINHEAP+P}->S
    {^^oMINHEAP+P+1}^^r->V

    //Call the POP subroutine
    POPS()

    //Write the parent's data
    S->{^^oMINHEAP+P}
    V->{^^oMINHEAP+P+1}^^r
    Return

Lbl POPS
    0->PARENT->P
    //Now loop until this parent is smaller than the children
    While 1
        PARENT*2+1->LCHILD+1->RCHILD
        ReturnIf LCHILD>=HEAPSIZE
        LCHILD*3->L
        If RCHILD<HEAPSIZE
            L+3->R
            If {^^oMINHEAP+R}<{^^oMINHEAP+L}
                R->L
                RCHILD->LCHILD
            End
        End

        ReturnIf {^^oMINHEAP+L}>=S
        {^^oMINHEAP+L}->{^^oMINHEAP+P}
        {^^oMINHEAP+L+1}^^r->{^^oMINHEAP+P+1}^^r
        LCHILD->PARENT
        L->P
    End
    Return

//This propagates an element up the heap
Lbl PROPUP
    [r1]->CHILD*3->C
    //If the child is at the root, it can't go up further.
    Return!If CHILD

    //Calculate the parent node
    CHILD-1/2->PARENT*3->P

    //Back up the child's score
    {^^oMINHEAP+C}->SCORE

    //If the parent is smaller, exit
    ReturnIf SCORE>={^^oMINHEAP+P}

    //back up the score of the child
    {^^oMINHEAP+C+1}^^r->VALUE

    //Call the prop-up subroutine
    PROPUS()

    //Finally, write the score and value to the child's new index
    SCORE->{^^oMINHEAP+C}
    VALUE->{^^oMINHEAP+C+1}^^r
Return

Lbl PROPUS
    While 1
        //Move the parent down
        {^^oMINHEAP+P}->{^^oMINHEAP+C}
        {^^oMINHEAP+P+1}^^r->{^^oMINHEAP+C+1}^^r
        //Child is now the parent
        PARENT->CHILD
        P->C
        //Exit if we are at the root
        Return!If CHILD
        //calculate next parent
        CHILD-1/2->PARENT*3->P

        //Exit if the new parent's score is smaller than the child's
        ReturnIf SCORE>={^^oMINHEAP+P}
    End

4
Axe / Re: Axe Q&A
« on: July 09, 2022, 07:55:30 pm »
I'm not sure what you mean, could you give an example of what you want to do?

As for Axe knowledge, I think I started using Axe around 11 years ago, so it's just experience. I've never been a heavy user of Axe since I was comfortable as an assembly programmer by the time I learned about it, but I know enough to make simple programs :) (Axe can get very convoluted in the hands of a pro.)

5
Axe / Re: Axe Q&A
« on: July 06, 2022, 07:13:13 am »
This
Code: [Select]
-8→{°MobOX+Mob}Is storing -8 as an 8-bit number.

At first, -8 is a 16-bit number stored as 65536-8 = 65528. That's works when your arithmetic is 16-bit. But when you store it as an 8-bit number, you lose the top 8 bits and it is stored as 256-8 = 248 instead.

Now when you read it, Axe has no idea that it used to be a signed 16-bit number, it's reading an 8-bit value that is 248 and in 16-bit, that's a positive number.

So what you need is to sign-extend the number where you copy the sign bit [top bit] of the 8-bit number into the top 8 bits of the 16-bit number. Luckily, Axe has a command for that: signed{<ptr>}

So whenever you are reading an 8-bit number and you want to tell Axe to interpret it as a signed number, you need to explicitly tell it.

6
Axe / Re: Axe Q&A
« on: July 03, 2022, 08:30:39 pm »
L1 is 768 bytes, so 768*8 = 6144 bits.

For reference, I'm using https://axe.eeems.ca/Commands.html to look things up. Eeems (an admin) hosts that Axe reference sheet and it's really handy

7
Axe / Re: Axe Q&A
« on: July 03, 2022, 08:25:57 pm »
L3 is safe as long as you aren't using grayscale (Axe uses it like a second "graph screen")


L2 uses the same memory as the OS's "statistics variables" so that'll clear that data, but that's usually fine since anybody who needs it can very easily regenerate the data.


L4 gets overwritten when you archive/unarchive.


L5 is overwritten when you draw text on the homescreen


L6 is overwritten when you draw to the graph screen


8
Axe / Re: Axe Q&A
« on: July 03, 2022, 08:09:09 pm »
That's assuming you have 8 bytes per row, but i think you might be mixing things up.

If you want 5 bytes per row (that's 40 bits total per row), you'd do  "{L1+(5*Y)+X}" where the 5 is how many bytes per row.

That's the code if you want a 5-by-5 array of 8-bit numbers

9
Axe / Re: Axe Q&A
« on: July 03, 2022, 08:02:16 pm »
Nah, that's not dumb :) A "bit" is a "binary digit" so a 0 or a 1. A 2-digit number has 102 (100) possible values, and a 7-bit number has 27 (128) possible values, so technically, you can fit a 2-digit number in 7 bits.

In reality, you'll usually be interacting with 8-bit and 16-bit  numbers (0-255 and 0-65535), so you'd just use an 8-bit value to store 2 digits.

Note: there are 8 bits per byte :)

10
Axe / Re: Axe Q&A
« on: July 03, 2022, 07:50:45 pm »
Not 25 variables per se, but 25 elements, so if you want 1-byte elements, you'd need 25 bytes :)

This is an example of where it's up to you how you want to store and retrieve the data, but commonly, people choose to store it row-by-row. The first five elements are the first row, the next five elements are the second row, and so on.

Arrays start at 0, so an easy (not necessarily best) implementation might be to refer to element (Y,X) as "{L1+(5*Y)+X}" where Y and X are between 0 and 4.

11
Axe / Re: Axe Q&A
« on: July 03, 2022, 07:39:06 pm »
In Axe, it's really low-level-- say you want 10, 1-byte elements. What you do is find (or allocate) a 10-byte chunk of RAM that is free, and you write and read bytes from it. For convenience Axe has L1 pointing to a 768-byte chunk of free RAM, so you can "{L1+2}→A" or "A→{L1+2}" to read/write the third element.

Axe has built-in ways to access 1- and 2-byte values, but in the end, it's up to you how you want to interpret the data :)

EDIT: A word of caution: Axe has no safety nets, so it won't stop you from reading or writing to data outside of your array on accident. If you aren't comfortable with arrays like this, make sure to back up your data in case you corrupt the data you have in RAM and need to clear RAM!

12
Math and Science / Re: A faster Newton's Method Square Root
« on: June 30, 2022, 11:29:30 pm »
Yup, I see no good reason for BCD floats. There is some usefulness to decimal floats, though-- they have the one advantage of BCD (don't have to be careful where base-10 representation is a must), but are nearly as efficient as binary floats in terms of storage. A 64-bit decimal64 has 16 digits of precision.

As for emulators, I use TIlem, but it does have glitches of it's own. One I found was it sometimes doesn't emulate the carry flag properly with add/adc/sbc on IX/IY, which was hell when testing some math routines :P I believe the problem is the emulator stores them internally as int32 or int64 and doesn't handle 16-bit overflow.

13
Math and Science / Re: A faster Newton's Method Square Root
« on: June 29, 2022, 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)

14
Math and Science / Re: A faster Newton's Method Square Root
« on: June 29, 2022, 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

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

Pages: [1] 2 3 ... 317