Jump to content
  • 1

atan2()


svenvandevelde
 Share

Question

As you know, I'm working on this game engine. One of the missing parts in the engine is to quickly calculate the angle between two points on the plane.
In my gaming logic, I'm already able to calculate the deltas for X and Y based on a given angle, using sin and cosin tables, but my biggest hurtle was to understand how to find the right way to make an enemy shoot a bullet from his machine to the player machine with a relevant accuracy (but not too accurate)...

That brought me to the topic of the arctan2 function, of which a lot is written. Every programming language imaginable has this function implemented. However ... that did not solve my issue for the CX16. How to quickly calculate a usable angle from two points on a plane on an 8 bit machine, where multiplication and division takes CPU time.

So I've been seaching the internet for a solution (I am not a matematician but learned sufficient maths in my studies, but forgot most of it).
Then one day, I stumbled on these two algorithms:
- Z80 CPU architecture - 8-bit atan2 | MSX Resource Center (Page 1/3)
- 6502 CPU architecture - base:8bit_atan2_8-bit_angle [Codebase 64 wiki]

The latter drew my immediate interest, and the more I started to analyze the assembly code, the less I understood what was going on...

;; Calculate the angle, in a 256-degree circle, between two points.
;; The trick is to use logarithmic division to get the y/x ratio and
;; integrate the power function into the atan table. Some branching is
;; avoided by using a table to adjust for the octants.
;; In otherwords nothing new or particularily clever but nevertheless
;; quite useful.
;;
;; by Johan Forslöf (doynax)

octant		= $fb			;; temporary zeropage variable

atan2		lda x1
		sbc x2
		bcs *+4
		eor #$ff
		tax
		rol octant

		lda y1
		sbc y2
		bcs *+4
		eor #$ff
		tay
		rol octant

		lda log2_tab,x
		sbc log2_tab,y
		bcc *+4
		eor #$ff
		tax

		lda octant
		rol
		and #%111
		tay

		lda atan_tab,x
		eor octant_adjust,y
		rts

This routine seems not to be a blast from the past, as it appears to be posted in 2015 somewhere on the site.
However, the way how the angle is calculated is rather genius ... (Although the creator is saying it's nothing special ..., I admire the intellect behind this).

So I decided to study it a bit more in depth what is going on here ...

 

The routine accepts two 8 bit 2D coordinates, so an (x1,y1) and (x2,y2), and calculates an "angle" between 0 and 255!

It first calculates the "slope" between the two points.
As we all know, to calculate a slope, one needs to "divide the y over x" (or the other way around), and executing a division on an 8-bit machine requires a proprietary algorithm to be written with the risk of consuming too much CPU. However, what this algorithm does, is uses a base 2 logarithm table that applies the Logarithm quotient rule:

image.thumb.png.7ab346c05a392da042a2e934e0036e75.png

In other words, using the logarithm table, it is very fast to calculate the quotient of the X/Y by subtracting the logarithm of X over the logarithm of Y.

		lda log2_tab,x
		sbc log2_tab,y

 

The other concept that the atan2 routine implements, is the angle calculation over 8 "octants" in a circle (there are 4 quadrants in a circle) ... It does this by examining 3 essential parameters of the input: the sign of the x and y coordinates, and then when x is divided over y, to determine if x is greater than y or vise versa. This takes most of the code, and instead of writing a lot of branches, the logic implements the selection of the octant segment using an assembler trick using the carry flag!

octant		= $fb			;; temporary zeropage variable

The logic builds up the octant variable gradually, which essentially contains the results of the carry flag shifted to the left at each of the calculation steps.

First, the absolute value of x is determined, and the corresponding segments in the octant model is determined, whether x1 is smaller than x2. When x1 is smaller than x2, then the carry will be set and will be shifted into the octant variable! So if x1 < x2, then the carry will be set, and the eor #$ff will make the negative result "positive", but it seems not to do this using the 2s complement rule (eor $#ff, clc, adc $#01). I think he did not implement 2s complement because the logic anyway achieves an approximation, and 2nd the carry bit would be cleared when clc would be used for the octant determination ...
Anyway, the octant variable will get a value %1 or %0 at this stage..., depending on the value of x1 and x2.

atan2		lda x1
		sbc x2
		bcs *+4
		eor #$ff
		tax
		rol octant

Second, the absolute value of  y is determined, and the corresponding segment in the octant model, whether y1 is smaller than y2. The resulting carry is left shifted into the octant variable, but bare in mind that the octant has already the octant segments of the x value embedded! So the octant values now will get a value %00, %01, %10 or %11, depending on the value of y1 and y2. Thus the quadrant in the octant model is calculated here.

		lda y1
		sbc y2
		bcs *+4
		eor #$ff
		tay
		rol octant

Third, the logaritmic devision is applied (as explained above) but also here the 3rd dimension in the octant model is determined, depending whether x is smaller than y. So the octant now can get value %000, %001, %010, %011, %100, %101, %110 or %111, and the resulting octant segment now is fully calculated.

		lda log2_tab,x
		sbc log2_tab,y
		bcc *+4
		eor #$ff
		tax

		lda octant
		rol
		and #%111
		tay

Note that the x register will contain the position to calculate the angle using the arctan table, and the y register will contain the 3 bit index to adjust the calculated 5-bit angle with the resulting octant segment!

The octant variable now has 8 possible values to calculate the angle, based on the calculated angle containing out of 5 bits in the 8-bit range using the arctan table ... Depending on the resulting value:

octant_adjust	.byte %00111111		;; x+,y+,|x|>|y|
		.byte %00000000		;; x+,y+,|x|<|y|
		.byte %11000000		;; x+,y-,|x|>|y|
		.byte %11111111		;; x+,y-,|x|<|y|
		.byte %01000000		;; x-,y+,|x|>|y|
		.byte %01111111		;; x-,y+,|x|<|y|
		.byte %10111111		;; x-,y-,|x|>|y|
		.byte %10000000		;; x-,y-,|x|<|y|

 

The last point to be explained is how the angle is calculated ... this is done using the pre-defined arctan table. The author does a trick, as the arctan table normally has a domain -pi/2 < y < pi/2, the atan table has the values populated in exponential order base 2 in 5 bits, but only from the lower domain (-pi/2 < y), excluding the value x = 0! In other words, it models a table of the values between x = -256 and x = -1 where the arctan table is populated with the expondential results of arctan(2^(x/32))*128/pi. A closer look will quickly identify that 128 is actually a simplification of 256/(pi*2) ... Thus, the resulting table contains values from $00 till $1f, which calculates the angle for octant segment 0. Again, $20 is not included as this would be the starting value of octant 1. The atan table actually models the resulting angle of the first segment in the octant model. The octant variable then will adjust the resulting angle to the correct octant depending on x1 - x2 values, y1 - y2 value and the resulting x and y value comparison.

I've modelled this out in geogebra, as part of the study, to fully understand what the arctan function is doing and how the angle is calculated for the first octant segment! 
See attached, but here is how the geogebra model looks like. Note that the functions implement the "floor()" method to eliminate any fractional number and to simulate how it would run on the 8 bit machine ...

image.thumb.png.47424b23e0e4e105f5c593989229b209.png

 

The green liine models the logarithm function log2(x)*scale, which is set in this example to 32.
The blue line is the actan function arctan(2^(x/scale))*width/(pi*2), with a width set to 256. This will result in angles between 0 and 63 for two octant segments 0 and 1.

Point A and B are the two points for which the atan is calculated. Move A and/or B but the function only implements the arctan, not the arctan2!

The geogebra model explains that when the AT point is in the lower domain of the arctan function, it returns the angle of point B from 0 to 31 degrees.

Now, I find that an angle of 256 possible values is too much, so my game logic implements and angle of 64 angle values, and that is more than enough! So, the actual octant model would be a subdivision of 3 bits instead of 5 bits, from 0 to 7.

Other point is the "resulution", it is not necessary to store for the log2 table 256 values, as the only thing I'm trying to accomplish, is to find the angle, and i can downsize the resolution from 640x480 to 160x120 for example. (by shifting the bits with 2 positions to the right), which requires me to only populate a table of 160 bytes ..., 

image.thumb.png.d6a169bb932a104830058930a6f83715.png

This would result in geogebra in the following settings (see the sliders) and the resulting angle). A scale of 16 and a width of 64 would allow me to only require 64 records in the arctan table, and 160 records in the log2 table, to calculate the angle between 0 and 7. I'm still studying a bit on how to optimize this and to actually implement all this in a working CX16 atan2 function, but i'll put that in a later post (as I'm progressing) ... Otherwise it becomes too much to write it all down ...

 

I'm not a mathematician, so not sure if the above explanation makes sense and any adjustment, recommendation or addtional info you want to share is welcome in this very interesting topic. I'm sure there are people here who have been doing this in the past already ...

 

Sven

  

 

 

 

 

 

ATAN2.ggb

Edited by svenvandevelde
  • Like 1
Link to comment
Share on other sites

20 answers to this question

Recommended Posts

  • 0

I did something similar for Chase Vault, while not a proper atan2 function, it did do a vector transformation, and enabled me to have a quick way to have the (stationary) Skulls shoot fireballs at the (moving) player. Depending on the level, the Skull will throw between 2 and 4 fireballs, one directly at the player and the others at a slight angle. My routine takes the current displacement vector between the skull and the player , and then converts that into a reversed motion vector for the fireball. The motion vector determines the number of pixels to move the fireball sprite every frame, in both X and Y directions. I do this using normalization tables in two banks of RAM, one for X and the other for Y. I can then quickly look up the motion vector based on the current displacement. Of course, this is very specific to my game as I have very well known bounds for these calculations, but this approach may also be generalized if you are just trying to do a similar thing. Having non-player entities firing at a target is pretty common, after all! Having all the extra RAM on the X16 makes using tables (like you already are for sin/cos) very attractive. Let some other computer do the math, and let the X16 have all the fun!

  • Like 1
Link to comment
Share on other sites

  • 0
On 4/19/2022 at 2:11 PM, SlithyMatt said:

I did something similar for Chase Vault, while not a proper atan2 function, it did do a vector transformation, and enabled me to have a quick way to have the (stationary) Skulls shoot fireballs at the (moving) player. Depending on the level, the Skull will throw between 2 and 4 fireballs, one directly at the player and the others at a slight angle. My routine takes the current displacement vector between the skull and the player , and then converts that into a reversed motion vector for the fireball. The motion vector determines the number of pixels to move the fireball sprite every frame, in both X and Y directions. I do this using normalization tables in two banks of RAM, one for X and the other for Y. I can then quickly look up the motion vector based on the current displacement. Of course, this is very specific to my game as I have very well known bounds for these calculations, but this approach may also be generalized if you are just trying to do a similar thing. Having non-player entities firing at a target is pretty common, after all! Having all the extra RAM on the X16 makes using tables (like you already are for sin/cos) very attractive. Let some other computer do the math, and let the X16 have all the fun!

Yes, there are multiple ways to calculate direction vectors. An other way is not use use atan2, but to calculate first the "distance" between the two points using the formula: distance = sqrt((x2-x1)^2 + (y2-y1)^2), and then to use the distance vector to calculate the unit vector and increment with a speed parameter. However, this formula construction may work fast on modern CPUs, it doesn't on an 8-bit machine, as you can observe in the formula one sqrt  and 2 exponential calculations. Of course, for those there are also faster mechanisms using lookup tables, but I really liked the elegance of the atan2 function approach :-). Hence the article.

I've posted a small prg that you can run on the cx16 that calculates the angle using the atan2 function. I've modified the atan2 function from the original article to have angle 0 at the y-axis, and clockwise incrementing to 15, 31, 47 and 63 (0) for each quadrant of the circle. As you move the mouse pointer, the angle is calculated from the middle point (319, 239). Note that I shift the coordinates with 2 bits to the right, so the coordinates displayed are between 159 and 119.

 

cx16-atan2.asm cx16-atan2.c cx16-atan2.prg

Link to comment
Share on other sites

  • 0

I struggled with this while making Rally Speedway 2020. I wanted the two cars to "bounce" away from each other when colliding. In order to do that I used the yellow car as reference point (origo in a coordinate system) and calculated what angle the blue car had in reference to the yellow using the horizontal and vertical distance. Because the cars are close to each other when colliding I simply used this precalculated atan2 table:

;Table for atan2 - which angle a vector (x,y) have in relation to origo. 256 = 360 degrees. Just for the first quadrant. 
_atantable:     ;rows x = 0 to 31, columns y = 0 to 31
        !byte    -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
        !byte    64,32,19,13,10, 8, 7, 6, 5, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1
        !byte    64,45,32,24,19,16,13,11,10, 9, 8, 7, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3
        !byte    64,51,40,32,26,22,19,16,15,13,12,11,10, 9, 9, 8, 8, 7, 7, 6, 6, 6, 6, 5, 5, 5, 5, 5, 4, 4, 4, 4
        !byte    64,54,45,38,32,27,24,21,19,17,16,14,13,12,11,11,10, 9, 9, 8, 8, 8, 7, 7, 7, 6, 6, 6, 6, 6, 5, 5
        !byte    64,56,48,42,37,32,28,25,23,21,19,17,16,15,14,13,12,12,11,10,10,10, 9, 9, 8, 8, 8, 7, 7, 7, 7, 7
        !byte    64,57,51,45,40,36,32,29,26,24,22,20,19,18,16,16,15,14,13,12,12,11,11,10,10,10, 9, 9, 9, 8, 8, 8
        !byte    64,58,53,48,43,39,35,32,29,27,25,23,22,20,19,18,17,16,15,14,14,13,13,12,12,11,11,10,10,10, 9, 9
        !byte    64,59,54,49,45,41,38,35,32,30,27,26,24,22,21,20,19,18,17,16,16,15,14,14,13,13,12,12,11,11,11,10
        !byte    64,59,55,51,47,43,40,37,34,32,30,28,26,25,23,22,21,20,19,18,17,16,16,15,15,14,14,13,13,12,12,12
        !byte    64,60,56,52,48,45,42,39,37,34,32,30,28,27,25,24,23,22,21,20,19,18,17,17,16,16,15,14,14,14,13,13
        !byte    64,60,57,53,50,47,44,41,38,36,34,32,30,29,27,26,25,23,22,21,20,20,19,18,18,17,16,16,15,15,14,14
        !byte    64,61,57,54,51,48,45,42,40,38,36,34,32,30,29,27,26,25,24,23,22,21,20,20,19,18,18,17,16,16,16,15
        !byte    64,61,58,55,52,49,46,44,42,39,37,35,34,32,30,29,28,27,25,24,23,23,22,21,20,20,19,18,18,17,17,16
        !byte    64,61,58,55,53,50,48,45,43,41,39,37,35,34,32,31,29,28,27,26,25,24,23,22,22,21,20,19,19,18,18,17
        !byte    64,61,59,56,53,51,48,46,44,42,40,38,37,35,33,32,31,29,28,27,26,25,24,24,23,22,21,21,20,19,19,18
        !byte    64,61,59,56,54,52,49,47,45,43,41,39,38,36,35,33,32,31,30,29,27,27,26,25,24,23,22,22,21,21,20,19
        !byte    64,62,59,57,55,52,50,48,46,44,42,41,39,37,36,35,33,32,31,30,29,28,27,26,25,24,24,23,22,22,21,20
        !byte    64,62,59,57,55,53,51,49,47,45,43,42,40,39,37,36,34,33,32,31,30,29,28,27,26,25,25,24,23,23,22,21
        !byte    64,62,60,58,56,54,52,50,48,46,44,43,41,40,38,37,35,34,33,32,31,30,29,28,27,26,26,25,24,24,23,22
        !byte    64,62,60,58,56,54,52,50,48,47,45,44,42,41,39,38,37,35,34,33,32,31,30,29,28,27,27,26,25,25,24,23
        !byte    64,62,60,58,56,54,53,51,49,48,46,44,43,41,40,39,37,36,35,34,33,32,31,30,29,28,28,27,26,26,25,24
        !byte    64,62,60,58,57,55,53,51,50,48,47,45,44,42,41,40,38,37,36,35,34,33,32,31,30,29,29,28,27,26,26,25
        !byte    64,62,60,59,57,55,54,52,50,49,47,46,44,43,42,40,39,38,37,36,35,34,33,32,31,30,30,29,28,27,27,26
        !byte    64,62,61,59,57,56,54,52,51,49,48,46,45,44,42,41,40,39,38,37,36,35,34,33,32,31,30,30,29,28,27,27
        !byte    64,62,61,59,58,56,54,53,51,50,48,47,46,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,30,29,28,28
        !byte    64,62,61,59,58,56,55,53,52,50,49,48,46,45,44,43,42,40,39,38,37,36,35,34,34,33,32,31,30,30,29,28
        !byte    64,62,61,59,58,57,55,54,52,51,50,48,47,46,45,43,42,41,40,39,38,37,36,35,34,34,33,32,31,31,30,29
        !byte    64,63,61,60,58,57,55,54,53,51,50,49,48,46,45,44,43,42,41,40,39,38,37,36,35,34,34,33,32,31,31,30
        !byte    64,63,61,60,58,57,56,54,53,52,50,49,48,47,46,45,43,42,41,40,39,38,38,37,36,35,34,33,33,32,31,31
        !byte    64,63,61,60,59,57,56,55,53,52,51,50,48,47,46,45,44,43,42,41,40,39,38,37,37,36,35,34,33,33,32,31
        !byte    64,63,61,60,59,57,56,55,54,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,36,35,34,33,33,32

  • Thanks 1
Link to comment
Share on other sites

  • 0
On 4/19/2022 at 1:45 PM, svenvandevelde said:

Yes, there are multiple ways to calculate direction vectors. An other way is not use use atan2, but to calculate first the "distance" between the two points using the formula: distance = sqrt((x2-x1)^2 + (y2-y1)^2), and then to use the distance vector to calculate the unit vector and increment with a speed parameter. However, this formula construction may work fast on modern CPUs, it doesn't on an 8-bit machine, as you can observe in the formula one sqrt  and 2 exponential calculations. 

You need to look at the Fast Inverse Square Root function as implemented in Quake.

 

  • Like 1
Link to comment
Share on other sites

  • 0
Posted (edited)
On 4/22/2022 at 8:28 PM, Johan Kårlin said:

I wanted the two cars to "bounce" away from each other when colliding. In order to do that I used the yellow car as reference point (origo in a coordinate system) and calculated what angle the blue car had in reference to the yellow using the horizontal and vertical distance.

Very nice approach. So a bouncing effect.

On 4/22/2022 at 8:28 PM, Johan Kårlin said:

;Table for atan2 - which angle a vector (x,y) have in relation to origo. 256 = 360 degrees. Just for the first quadrant. 

What means, the first quadrant in your situation? I mean, your input parameters are an x and a y coordinate. So how is the angle calculated for the "other" quadrants?

Edited by svenvandevelde
Link to comment
Share on other sites

  • 0
On 4/23/2022 at 4:14 AM, Ed Minchau said:

You need to look at the Fast Inverse Square Root function as implemented in Quake.

I've looked at this many, many times @Ed Minchau. It for sure is very interersting but not sure if this can be implemented for an 8 bit solution. Also this algorithm uses floats. Would a similar approach be possible using fixed point arithmatic, f.e. a 3 byte number system with the last byte the fractional part?

Link to comment
Share on other sites

  • 0
On 4/23/2022 at 7:32 AM, svenvandevelde said:

I've looked at this many, many times @Ed Minchau. It for sure is very interersting but not sure if this can be implemented for an 8 bit solution. Also this algorithm uses floats. Would a similar approach be possible using fixed point arithmatic, f.e. a 3 byte number system with the last byte the fractional part?

Nope, for fixed point you need a different approach. 

How much accuracy do you really need? Is 1% good enough? Because you really only need the top 8 bits if that's the case.

Link to comment
Share on other sites

  • 0
On 4/23/2022 at 3:30 PM, svenvandevelde said:

What means, the first quadrant in your situation? I mean, your input parameters are an x and a y coordinate. So how is the angle calculated for the "other" quadrants?

If the blue car is to the right, of the yellow car, above it or something in between those two positions it is in the first quadrant.

1. Let
dx = horizontal distance = x coordinate of blue car - x coordinate of yellow car
dy = vertical distance = y coordinate of blue car - y coordinate of yellow car

2. a = angle = look up value in table by using  |dx| and |dy|. 

3. if dx < 0 then take 128 - a (blue car is in second or third quadrant).

4. if dy < 0 then take 256 (=0) - a (blue car is in fourth quadrant)

This works as long the distance between the objects (in my case cars) are no more than 31 units horzontally and vertically in your "world" coordinate system. In other words, usable for bouncing effects.

  • Like 1
Link to comment
Share on other sites

  • 0
On 4/23/2022 at 9:55 PM, Ed Minchau said:

Nope, for fixed point you need a different approach. 

How much accuracy do you really need? Is 1% good enough? Because you really only need the top 8 bits if that's the case.

1% is more than enough. But will not use float (slow).

How would this look like for an 8 bit machine?

Link to comment
Share on other sites

  • 0
On 4/24/2022 at 12:43 PM, svenvandevelde said:

1% is more than enough. But will not use float (slow).

How would this look like for an 8 bit machine?

To get this to work on an 8 bit machine, ideally you only want to work with single byte parameters. 

If the delta X and delta Y can be expressed as single bytes (say in the range of -127 to 127), then this can be simplified a lot.

You've got two bytes representing the integer part and one byte as the fractional part for each of X and Y, yes? So what is the maximum distance between an enemy machine and the player machine for which you need to calculate a firing direction? 

If you can scale the delta X and delta Y to [-127..127], then a lot of calculations can collapse into lookup tables. I've been treating that range as equivalent to [-1..1].

I faced a similar problem to yours in Asteroid Commander for the starfield. I had the Right Ascension and declination for a list of stars, and needed to determine whether a star was in the field of view,its distance from the center of the view, and an angle from an arbitrary vector (because the view can be rotated).

So, I needed to convert spherical to Cartesian coordinates for the center of the view and for each star relative to that spot in the sky. Then I needed only those stars within a certain distance range (limited by the edge of the view and the asteroid in the middle), and then I needed a square root function for the distance and a dot product and division and an arcosine function to get that angle.

I managed to simplify the calculations though. I originally had 64 arcosine tables, and reduced that to a single table that assumes the denominator (the distance) is 64. There are three tables that use the high byte of the sum of squares as their indices: a square root table, a table that indicates the number L of left shifts required to get that square root value into the range of 64..127, and a factor F to multiply that value by to get the denominator to 64; the dot product in the numerator is what actually gets doubled L times and multiplied by F, and the result is the index into the arcosine table. It ends up only taking less than 1000 cycles to get the distance and angle value for a star this way, including the 5 to 7 multiplications involved. 

Edited by Ed Minchau
Link to comment
Share on other sites

  • 0

This topic got me thinking.  I've been using a 1.7 bit notation for a lot of calculations over these last few years of 8 bit programming.  This is just the numbers -1 to 1 expressed using the range -127 to 127. So far I have developed quite a few subroutines and lookup tables to enable a lot of fast 8 bit math.

There's easy ones, like lookup tables for sine and cosine, more complex like multiplication and division and arcosine, and if I dig through some old spreadsheets I know I've got atan2 and sigmoid and other functions.

Although these functions aren't 100% accurate,  they are generally quite close. What they are, however, is fast. Multiplying two numbers takes on average 80 cycles (the inputs are both in the range [-1..1], so the output is also in that range, and only one byte).

What I'm thinking of doing is collecting all those tables and functions in a single 8kb block,  meant to be stored in banked RAM, and then just having a jump table at BF80-BFFF as the interface. Sort of a mini-kernel for very fast fixed point single byte variables. 

Interested?

  • Like 1
Link to comment
Share on other sites

  • 0
On 4/30/2022 at 12:03 AM, Ed Minchau said:

This topic got me thinking.  I've been using a 1.7 bit notation for a lot of calculations over these last few years of 8 bit programming.  This is just the numbers -1 to 1 expressed using the range -127 to 127. So far I have developed quite a few subroutines and lookup tables to enable a lot of fast 8 bit math.

There's easy ones, like lookup tables for sine and cosine, more complex like multiplication and division and arcosine, and if I dig through some old spreadsheets I know I've got atan2 and sigmoid and other functions.

Although these functions aren't 100% accurate,  they are generally quite close. What they are, however, is fast. Multiplying two numbers takes on average 80 cycles (the inputs are both in the range [-1..1], so the output is also in that range, and only one byte).

What I'm thinking of doing is collecting all those tables and functions in a single 8kb block,  meant to be stored in banked RAM, and then just having a jump table at BF80-BFFF as the interface. Sort of a mini-kernel for very fast fixed point single byte variables. 

Interested?

I think a strong argument can be made that such a thing could live in ROM.

  • Like 1
Link to comment
Share on other sites

  • 0
On 5/1/2022 at 2:42 AM, Scott Robison said:

I think a strong argument can be made that such a thing could live in ROM.

Indeed. Programs could focus on the actual logic rather than having to deal with these calculations.

A separate ROM bank containing such functions would be really useful.

 

Link to comment
Share on other sites

  • 0
On 4/30/2022 at 8:03 AM, Ed Minchau said:

This topic got me thinking.  I've been using a 1.7 bit notation for a lot of calculations over these last few years of 8 bit programming.  This is just the numbers -1 to 1 expressed using the range -127 to 127. So far I have developed quite a few subroutines and lookup tables to enable a lot of fast 8 bit math.

There's easy ones, like lookup tables for sine and cosine, more complex like multiplication and division and arcosine, and if I dig through some old spreadsheets I know I've got atan2 and sigmoid and other functions.

Although these functions aren't 100% accurate,  they are generally quite close. What they are, however, is fast. Multiplying two numbers takes on average 80 cycles (the inputs are both in the range [-1..1], so the output is also in that range, and only one byte).

What I'm thinking of doing is collecting all those tables and functions in a single 8kb block,  meant to be stored in banked RAM, and then just having a jump table at BF80-BFFF as the interface. Sort of a mini-kernel for very fast fixed point single byte variables. 

Interested?

very

Link to comment
Share on other sites

  • 0
Posted (edited)

I haven't dug through the code of the new release, but I did go back to some stuff I did way back in 2018 on this idea and wrote out some code. Including the JSR and a JMP redirect and RTS, multiplication takes on average 83 cycles, division takes on average 110 cycles, and my atan2 function takes 250-300 cycles.  

Edited by Ed Minchau
Link to comment
Share on other sites

  • 0
On 5/1/2022 at 11:42 AM, Ed Minchau said:

I haven't dug through the code of the new release, but I did go back to some stuff I did way back in 2018 on this idea and wrote out some code. Including the JSR and a JMP redirect and RTS, multiplication takes on average 83 cycles, division takes on average 110 cycles, and my atan2 function takes 250-300 cycles.  

haven't counted the cycles yet but it will be less ... also i store 64 bytes as lookup tables, that's it.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

×
×
  • Create New...

Important Information

Please review our Terms of Use