gbadev.org forum archive

Right, I'm working on the next stage of libQWDS and I need a TAN function.

Thing is, I don't want to include libm because at 388k it's not something I want to have as a required link for a library that is, at the moment, only 2-3k in size.

I've been googling for something but only came up with a few results. I found, among other things, the OSS release of Sun's libm and was thinking of using their TAN function but there is one issue. Their libm source is licensed under the CDDL OpenSolaris licensen while I've placed libQWDS under LGPL.

I'm not sure whether I should bite the bullet and change licenses in order to implement tha TAN code I need.

Anyone got any advice they could offer on this?

On a side note, I'm not worried too much about the TAN function's speed, as it's not going to be used in an on-the-fly fashion (Actually, it's going to be used for generatig TAN tables than can be used in an on-the-fly fashion :-) And yes, I am aware libnds includes TAN look-up tables, but I want to be able to generate custom tables for libQWDS without relying on libnds being there...)
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI

You can find my NDS homebrew projects here...

If you are not worried by speed, take a look at the correspondig taylor chain:

[Images not permitted - Click here to view it]

The deeper you calculate it (the greater your n is) the more precise it will be.

But i still advise using the lookup tables for sin & cos, and doing a simple Divistion to them. (tan = sin/cos)
_________________
GBAMP Multiboot

I don't know what license this Perl module is under:
Please use the [url=] syntax for long URLs -- MOD

You could actually just go to search.cpan.org, but I was using Google Codesearch to find stuff.

Actually, I don't even know if I'm following that code around right. Maybe it's not even useful. I didn't see anything that seemed to call external C code or something, but then again I'm no expert at Perl.

Last edited by tyraen on Mon Dec 18, 2006 7:07 pm; edited 1 time in total

Yeah, I did think about using the Taylor series...

While I am not too worried about speed, I would also prefer that the init function for libQWDS doesn't suddenly go from being a light call to something that takes a minute or more to finish...

I don't want to use the look-up tables from libnds because, unless there's something I don't know, they go up in integer increments...

That's fine for a normal look-up, for the version of libQWDS that supports a custom number of zones I'd prefer to have my own TAN function for reasons such as: I decide to use 7 zones, which means I need to work out tangents based on 2PI / x, where x is the number of segments. 2PI/7 gives a radian value that doesn't translate to a nice round number of degrees (Comes in at around 51.4......... degrees actually)

So I would rather prefer that I have my own TAN function to use for generating my tan tables because they're custom tables that are not confined to nice round integers.

The values stored in the tan tables themselves are fixed-point-erised like the libnds values, but I would prefer to generate my FP tan values from accurate output, rather than already FPed look-up tables...

Maybe I will implement the taylor chain then :-)

The Sun library doesn't seem to be much use on closer inspection. Most of the actual trig functions are in x86 assembler...
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI

You can find my NDS homebrew projects here...

OOPMan wrote:

Maybe I will implement the taylor chain then :-)

You have seen the n! and the Bernulli number in there ? ;)
_________________
GBAMP Multiboot

Not a complete Taylor series, a limited one...

If I recall from my Maths at varsity, even a few terms in a Taylor series allow for pretty accurate values to be generated...

Using only two terms to generate than tan of PI/4 (45 degrees) produces a value around 0.98......., which is very close to 1 :-)

Add a few more terms, making it maybe 5 in total and it would probably be close enough for my needs...

Of course, I guess I would still need to speed test and see just how much of a performance hit it would introduce to the init function. It is an init function and is meant to be called only once and before anything else is done, so even 10 seconds wouldn't be that bad...

Bah, just have to see, I guess :-)
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI

You can find my NDS homebrew projects here...

Hmmmm, I've found something that will hopefully solve my problems without requiring a reduced Taylor series...

It's called CORDIC and allows you to generate sin and cosine values quite nicely on systems without an FPU...

Anyway, assumng I can use it to generate sin and cosine, tan is just a division away :-)
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI

You can find my NDS homebrew projects here...

Quote:

Using only two terms for tan of PI/4 produces a value around 0.98
which is very close to 1

a short taylor works pretty well between -pi/4..+pi/4 but not much further.
you can use tan(x) = 1.0/tan(pi/2-x) for the other half.
_________________
"The three chief virtues of a programmer are: Laziness, Impatience and Hubris"

I'd say lookup table with linear interpolation between elements.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

Yeah, CORDIC is out, because it needs math lib functions to work...

At the moment I'm going to code for three options, selectable at compile time with defines...

1: Standard math lib tab (For those who already are linking libm in)
2: The limited taylor chain, for shits and giggles...
3: Interpolation using the trig_lut.h included with libnds

If I'm feeling jumpy I may add in CORDIUC as an option later, if I can understand the damn thing...

The Taylor chain being limited to |x| < PI/2 is not a major problem though and accuray is not such a big issue either, since the numbers are going to be FixedPoiner'ised anyway and thus lose accuracy whatever happens :-)

Also, I was kicking myself for not thinking of it sooner, but went and downloaded the libc source and will maybe look into pulling the sin/cos implementations from there, assuming they don't introduce too much extra source code :-)
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI

You can find my NDS homebrew projects here...

Quote:

The Taylor chain being limited to |x| < PI/2 is not a major problem though and accuray is not such a big issue either

did you realize that tan is approaching infinity near PI/2 ?
_________________
"The three chief virtues of a programmer are: Laziness, Impatience and Hubris"

Yeah, course I do :-)

That's way it's |x| < PI/2, not |x| <= PI/2 :-)

It can approach infinity all it wants, but while it's being stored in a float it can only come so close ;-)
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI

You can find my NDS homebrew projects here...

OOPMan wrote:

It can approach infinity all it wants, but while it's being stored in a float it can only come so close ;-)

Sure you don't mean the opposite? IEEE floating point does support infinity...

Hrrrmmm, is that the case? How exactly do they encode an infinite amount of data then? Some kind of parallel universe tech?

It may support the concept of infinity and you might be able to assign it a value labelled Infinity, Without All the Data, but it's not the same as an endless stream of bits that burns a whole in your CPU, memory, mind and just about everything else...

In the context of tha Tan implementation what I meant was that it's not a problem.

If we keep in mind that the libQWDS context will support a maximum of 255 zones, hence the smallest angle will be 2PI/255.

While the tan of 89.9999999999999999999999999999... etc degrees may well approach infinity, in the context of libQWDS it's not an issue...
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI

You can find my NDS homebrew projects here...

Quote:

[..] hence the smallest angle will be 2PI/255.

ah ok, sorry - i thought we're talking about real math ;)
_________________
"The three chief virtues of a programmer are: Laziness, Impatience and Hubris"

Hehehe, the Pure Math vs. Applied Math divide :-)

Or something :-)

My application is pretty limited, so I'm happy :-)
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI

You can find my NDS homebrew projects here...

OOPMan wrote:

Thing is, I don't want to include libm because at 388k it's not something I want to have as a required link for a library that is, at the moment, only 2-3k in size.

You do realise that linking against a library doesn't pull in the entire contents of that library?

The size of a .a file bears little relation to the size added to a binary after final linking and stripping of the debug information.

Not that I'm saying you *should* use libm, merely that basing your decision on the size of the raw library is wrong.
_________________
devkitPro - professional toolchains at amateur prices
devkitPro IRC support
Personal Blog

Hmmm, thanks for that wintermute. I was honestly not aware of that. I'll try doing a test static link just to see how big it is.

Still, if it more than double the size of the library I'll discard that option by default (Although it can be optionally enabled for those people already using libm :-)
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI

You can find my NDS homebrew projects here...

OOPMan wrote:

Hrrrmmm, is that the case? How exactly do they encode an infinite amount of data then? Some kind of parallel universe tech?

Infinite is not a number (A sepcial case of no number tho)

Refer definition of setN: it is impossible to create infinite by 0 and "++" (successor). SetN in itself tho is infinite.
(|SetN| = inf) & (inf not ? SetN)

Therefor it does not have to store the numbers content, but a flag infinite!. The thing inaccuracy comes in is thinking too big numbers are inifinite ;)

IEEE Encoding for inifinites: +/- bit valid, exponent = all bits set, mantisse = 0

:edit: on s siednote, there is even a bigger 'thing' then infinite. Where |SetN| is infinite by definition, setR is not countable, meaning there is no injective function setR -> setN, but from setN into setR. Therefor is |SetR| > |SetN| = inf
_________________
GBAMP Multiboot

Mighty Max wrote:

I couldn't tell if you already knew this, but there are varying degrees of cardinality, and therefore varying "sizes" for infinity. Once again, wikipedia has somthing to say about Aleph Numbers. The set of natural numbers has cardinality Aleph-null.
_________________
http://chishm.drunkencoders.com
http://dldi.drunkencoders.com

Yes, i know about the different cardinalities. (The name Aleph-Number was new to me)

We can scale it up until we set infinite = cardinality of the class of all sets. :D
But i prefer to think of |setN| as infinite, and everything bigger as less finiter then infinite ;)

(Note: class, because set of all sets would be element of itself, which would invalidate the definition)
_________________
GBAMP Multiboot

Mighty Max wrote:

Therefor it does not have to store the numbers content, but a flag infinite!. The thing inaccuracy comes in is thinking too big numbers are inifinite ;)

Really, when it comes to floating point "infinite" just means "too large/small".
_________________
I'm a PSP hacker now, but I still <3 DS.

Yes, sets of infinity :-) A guy I knew doing 3rd-year Maths mentioned that stuff :-) It sounds really cool, even to someone like me who is, essentially, crap at maths :-)
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI

You can find my NDS homebrew projects here...

Forgive me if I am spouting nonsense but could you not use the SINE bios function and the fact
tanX= sinX / cosX
and if you have to cosX = sin ( pi/2 - X )

edit: My bad it is a table not a function. It is in the ARM7 BIOS if wondered though: http://nocash.emubase.de/gbatek.htm#biosmiscfunctions

Last edited by FAST6191 on Thu Dec 21, 2006 2:12 pm; edited 2 times in total

There's a sin function built into the NDS's BIOS? Or is that built into the ARM?

Anyone else know about such a thing?

You're not talking about ther libnds trig look-up tables are you?
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI

You can find my NDS homebrew projects here...

Not sure about sine-support in the ds-rom, but this is the sin/cos-implementation I use in my gba-stuff. The idea is to have a LUT for 90 degrees of the sine-wave, and mirroring to get the full 360 degrees. Then linear-interpolation is used for more accuracy. 360 degrees map to 1 << 16 here also.

math.c:

Code:

#ifndef MATH_H
#define MATH_H

#define SIN_TABLE_LOG2_SIZE 9
#define SIN_TABLE_SIZE (1 << SIN_TABLE_LOG2_SIZE)
extern const unsigned short sin_lut[(SIN_TABLE_SIZE / 4) + 1];

inline int fixed_fsin(int i)
{
int idx = i & ((SIN_TABLE_SIZE >> 2) - 1);
switch ((i >> (SIN_TABLE_LOG2_SIZE - 2)) & 0x3)
{
   case 0: return +int(sin_lut[idx]);
   case 1: return +int(sin_lut[(SIN_TABLE_SIZE / 4) - idx]);
   case 2: return -int(sin_lut[idx]);
   case 3: return -int(sin_lut[(SIN_TABLE_SIZE / 4) - idx]);
}
assert(0); // should not happen. ever.
}

inline int fixed_fcos(int i)
{
return fixed_fsin(i + (SIN_TABLE_SIZE / 4));
}

#define ASDSDF (16 - SIN_TABLE_LOG2_SIZE)
static inline int fixed_sin(int i)
{
const unsigned index = unsigned(i) >> ASDSDF;
const int v0 = fixed_fsin(index);
const int v1 = fixed_fsin(index + 1);
int diff = v1 - v0;
int t = i & ((1 << ASDSDF) - 1);
return v0 + ((diff * t) >> ASDSDF);
}

static inline int fixed_cos(int i)
{
const unsigned index = unsigned(i) >> ASDSDF;
const int v0 = fixed_fcos(index);
const int v1 = fixed_fcos(index + 1);
int diff = v1 - v0;
int t = i & ((1 << ASDSDF) - 1);
return v0 + ((diff * t) >> ASDSDF);
}
#undef ASDSDF

#endif /* MATH_H */

math.cpp:

Code:

#include "math.h"

const unsigned short sin_lut[(SIN_TABLE_SIZE >> 2) + 1] =
{
0x0000, 0x0324, 0x0648, 0x096c, 0x0c8f, 0x0fb2, 0x12d5, 0x15f6, 0x1917, 0x1c37,
0x1f56, 0x2273, 0x258f, 0x28aa, 0x2bc3, 0x2edb, 0x31f1, 0x3505, 0x3816, 0x3b26,
0x3e33, 0x413e, 0x4447, 0x474c, 0x4a4f, 0x4d4f, 0x504d, 0x5347, 0x563e, 0x5931,
0x5c21, 0x5f0e, 0x61f7, 0x64dc, 0x67bd, 0x6a9a, 0x6d73, 0x7048, 0x7319, 0x75e5,
0x78ac, 0x7b6f, 0x7e2e, 0x80e7, 0x839b, 0x864a, 0x88f5, 0x8b99, 0x8e39, 0x90d3,
0x9367, 0x95f6, 0x987f, 0x9b02, 0x9d7f, 0x9ff6, 0xa266, 0xa4d1, 0xa735, 0xa993,
0xabea, 0xae3b, 0xb085, 0xb2c8, 0xb504, 0xb739, 0xb967, 0xbb8e, 0xbdae, 0xbfc6,
0xc1d7, 0xc3e1, 0xc5e3, 0xc7dd, 0xc9d0, 0xcbbb, 0xcd9e, 0xcf79, 0xd14c, 0xd317,
0xd4da, 0xd695, 0xd847, 0xd9f1, 0xdb93, 0xdd2c, 0xdebd, 0xe045, 0xe1c4, 0xe33b,
0xe4a9, 0xe60e, 0xe76a, 0xe8be, 0xea08, 0xeb4a, 0xec82, 0xedb1, 0xeed7, 0xeff4,
0xf108, 0xf212, 0xf313, 0xf40a, 0xf4f9, 0xf5dd, 0xf6b9, 0xf78a, 0xf852, 0xf911,
0xf9c6, 0xfa72, 0xfb13, 0xfbab, 0xfc3a, 0xfcbe, 0xfd39, 0xfdaa, 0xfe12, 0xfe6f,
0xfec3, 0xff0d, 0xff4d, 0xff83, 0xffb0, 0xffd2, 0xffeb, 0xfffa, 0xffff
};

edit: uh, corrected what was in what file, and added an include-guard ;)

Last edited by kusma on Thu Dec 21, 2006 5:36 pm; edited 1 time in total

A nice compact little bit of code there kusma, plus it has hexes :-)

BTW, why is math.h include? I don't see any math functions...
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI

You can find my NDS homebrew projects here...

OOPMan wrote:

A nice compact little bit of code there kusma, plus it has hexes :-)

BTW, why is math.h include? I don't see any math functions...

it's my math.h-file, the one above - not stdlibs math.h ;)

Now I feel like a right melon :-)
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI

You can find my NDS homebrew projects here...

OOPMan wrote:

There's a sin function built into the NDS's BIOS? Or is that built into the ARM?

There's a sin/cos in the GBA BIOS (called ObjAffineSet) but not the DS.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

Hmmmmmm, what happens to GBA games running on the DS that need that? Errors and the like?

Interesting to know, though...
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI

You can find my NDS homebrew projects here...

The rom blended in in DS mode and GBA mode are not the same. A prog running in GBA mode can access this swi.
_________________
GBAMP Multiboot

Yep, that's why GBA mode still has the bootup sequence when it doesn't exist anywhere in DS BIOS/firmware. Would have been neat if they made that accessible from DS mode, if only so we could still use the functions they took out.
_________________
I'm a PSP hacker now, but I still <3 DS.

gbadev.org forum archive

DS development > Looking for a TAN implementation...

#112614 - OOPMan - Mon Dec 18, 2006 6:31 pm

#112616 - Mighty Max - Mon Dec 18, 2006 6:43 pm

#112617 - tyraen - Mon Dec 18, 2006 7:06 pm

#112618 - OOPMan - Mon Dec 18, 2006 7:06 pm

#112619 - Mighty Max - Mon Dec 18, 2006 7:12 pm

#112621 - OOPMan - Mon Dec 18, 2006 7:19 pm

#112628 - OOPMan - Mon Dec 18, 2006 9:27 pm

#112736 - hellfire - Tue Dec 19, 2006 11:20 pm

#112743 - tepples - Tue Dec 19, 2006 11:58 pm

#112793 - OOPMan - Wed Dec 20, 2006 9:31 am

#112797 - hellfire - Wed Dec 20, 2006 10:21 am

#112798 - OOPMan - Wed Dec 20, 2006 10:38 am

#112801 - kusma - Wed Dec 20, 2006 11:24 am

#112803 - OOPMan - Wed Dec 20, 2006 11:47 am

#112808 - hellfire - Wed Dec 20, 2006 12:51 pm

#112809 - OOPMan - Wed Dec 20, 2006 1:25 pm

#112810 - wintermute - Wed Dec 20, 2006 1:47 pm

#112813 - OOPMan - Wed Dec 20, 2006 2:10 pm

#112816 - Mighty Max - Wed Dec 20, 2006 2:37 pm

#112873 - chishm - Thu Dec 21, 2006 12:00 am

#112877 - Mighty Max - Thu Dec 21, 2006 12:22 am

#112891 - HyperHacker - Thu Dec 21, 2006 6:37 am

#112897 - OOPMan - Thu Dec 21, 2006 8:52 am

#112907 - FAST6191 - Thu Dec 21, 2006 1:54 pm

#112908 - OOPMan - Thu Dec 21, 2006 2:04 pm

#112912 - kusma - Thu Dec 21, 2006 2:39 pm

#112915 - OOPMan - Thu Dec 21, 2006 4:03 pm

#112917 - kusma - Thu Dec 21, 2006 4:20 pm

#112920 - OOPMan - Thu Dec 21, 2006 5:06 pm

#112925 - tepples - Thu Dec 21, 2006 6:07 pm

#112926 - OOPMan - Thu Dec 21, 2006 6:11 pm

#112929 - Mighty Max - Thu Dec 21, 2006 6:19 pm

#112955 - HyperHacker - Thu Dec 21, 2006 11:41 pm