OSDev.org

The Place to Start for Operating System Developers
It is currently Tue Nov 24, 2020 8:26 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: Implementing a math library
PostPosted: Sun Oct 11, 2020 3:04 pm 
Offline
Member
Member

Joined: Wed Feb 19, 2020 1:08 pm
Posts: 63
Location: Italy
I've choosed to reimplement the standard c library in my OS to have more controll on what is happening. I'm still implementing all the functionalities that aren't directly bound to the kernel such as string manipulation functions leaving others like malloc fot later. In this way when I'll start to implement some serious stuffs on the kernel I'll have a soldi std library to rely on.
It was going all well since I've faced the math.h header: I've tried to implement some functions such as sin, cos and log10 using various approximations but were very imprecise and slow. Is there a page, paper, book or something you could suggest me to implement this stuffs? By now I've tried only pure mathematical methods but there could be some bit manipulation methods that I don't know.
What can i do?


Top
 Profile  
 
 Post subject: Re: Implementing a math library
PostPosted: Sun Oct 11, 2020 4:47 pm 
Online
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 2476
Bonfra wrote:
sin, cos

It's a lot easier to come up with good approximations for sin() and cos() if you can ensure the argument will always be within a small range, such as (-π/4,π/4). Here's a paper about argument reduction. It's possible to implement this argument reduction using only integer operations, which I think is easier than using floating point operations.

If the reduced argument is sufficiently small, sin() returns the reduced argument, and cos() returns 1. With that, you can further reduce the range over which your approximations need to be accurate, although you may find this step to be unnecessary.

Note that the argument reduction algorithm presented in the paper I linked above includes r = f·(π/2) for the final step of computing the reduced argument. You'll get some odd results if you forget that step!

Unfortunately, that's as far as I've gotten - I don't have any good approximations for sine or cosine after the argument is appropriately reduced.


Top
 Profile  
 
 Post subject: Re: Implementing a math library
PostPosted: Sun Oct 11, 2020 8:40 pm 
Offline
Member
Member

Joined: Wed Mar 30, 2011 12:31 am
Posts: 407
Some mathematical functions are available directly from the FPU on your target platform.

For things like sine/cosine, a common approach after argument reduction is to use a table. For better results, you can lerp between the neighboring table entries to get smooth transitions.

_________________
toaruos on github | toaruos.org | gitlab | twitter | bim - a text editor


Top
 Profile  
 
 Post subject: Re: Implementing a math library
PostPosted: Sun Oct 11, 2020 9:36 pm 
Online
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 2476
klange wrote:
Some mathematical functions are available directly from the FPU on your target platform.

True, but they may not be suitable for a general-purpose math library. For example, the x86 FSIN, FCOS, FSINCOS, and FPTAN instructions can produce inaccurate results due to imprecise argument reduction, and they're only valid when the input is within the range (-2⁶³,2⁶³).

I'm not sure about FPTAN, but you can solve the problems with the other three instructions by reducing the argument yourself using the method outlined in that paper I linked above. (But note that they always operate with 64 bits of precision, even when you don't need a long double, so using a table or a polynomial approximation may still be faster.)

klange wrote:
For things like sine/cosine, a common approach after argument reduction is to use a table.

If you're optimizing for speed, make sure you benchmark against a polynomial approximation. The cache miss(es) from using a table might be so expensive that the polynomial is faster.


Top
 Profile  
 
 Post subject: Re: Implementing a math library
PostPosted: Mon Oct 12, 2020 2:23 am 
Offline
Member
Member

Joined: Wed Oct 01, 2008 1:55 pm
Posts: 2318
I think the table approach is best for more custom applications like signal analysis where the precision of the argument & result is given, which also results in optimal table sizes. For instance, if the argument is 16 bits, using 64 k table entries makes it possible to calculate sin() and cos() with only two look-ups and almost no overhead. I don't think this can be beaten. The table entries could also be parts (integers), as many of these applications will work on integers rather than floating-point data.

For more general-purpose uses, the FPU is probably the best alternative. It already has the smart algorithms built-into the hardware and so the performance is not likely to be better if the normal CPU is used.

Of course, if you want sin() and cos() with higher precision than the FPU can deliver, then a custom approach might be warranted.

Scaling the arguments will be necessary regardless of the method used.


Top
 Profile  
 
 Post subject: Re: Implementing a math library
PostPosted: Tue Oct 20, 2020 12:13 am 
Offline
Member
Member

Joined: Wed Feb 19, 2020 1:08 pm
Posts: 63
Location: Italy
Tanks to all for the suggestions, I'm working hard on implementing them, I'll let you know when I'm at a good point. :)


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: foliagecanine, Google [Bot] and 13 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group