How to compute the sine function, on a CPU with no FPU.

There exists a maxim in the publishing world, which is, ‘Publish or Perish.’ I guess it’s a good thing I’m not a publisher, then. In any case, it’s been a while since I posted anything, so I decided to share with the community some wisdom that existed in the early days of computing, and when I say that, it really means, ‘back in the early days’. This is something that might have been used on mini-computers, or, on the computers in certain special applications, before PCs as such existed.

A standard capability which should exist, is to compute a decently accurate sine function. And one of the most lame reasons could be, the fact that audio files have been encoded with an amplitude, but that a decoder, or speech synthesis chip, might only need to be able to play back a sine-wave, that has that encoded peak amplitude. However, it’s not always a given that any ‘CPU’ (“Central Processing Unit”) actually possesses an ‘FPU’ (a “Floating-Point Unit”). In such situations, programmers back-when devised a trick.

It’s already known, that a table of pre-computed sine functions could be made part of a program, numbering maybe 256, but that, if all a program did was, to look up sine values from such a table once, ridiculously poor accuracies would initially result. But it was also known that, as long as the interval of 1 sine-wave was from (zero) to (two-times-pi), the derivative of the sine function was the cosine function. So, the trick, really, was, to make not one lookup into the table, but at least two, one to fetch an approximate sine value, and the next, to fetch an approximate cosine value, the latter of which was supposedly the derivative of the sine value at the same point. What could be done was, that a fractional part of the parameter, between table entries, could be multiplied by this derivative, and the result also added to the sine value, thus yielding a closer approximation to the real sine value. (:3)

But, a question which readers might have about this next could be, ‘Why does Dirk not just look up two adjacent sine-values, subtract to get the delta, and then, multiply the fractional part by this delta?’ And the answer is, ‘Because one can not only apply the first derivative, but also the second derivative, by squaring the fractional part and halving it (:1), before multiplying the result from that, by the negative of the sine function!’ One obtains a section of a parabola, and results from a 256-element table, that are close to 16 bits accurate!

The source code can be found in my binaries folder, which is:

https://dirkmittler.homeip.net/binaries/

And, in that folder, the compressed files of interest would be, ‘IntSine.tar.gz’ and ‘IntSine.zip’. They are written in C. The variance that I get, from established values, in (16-bit) integer units squared, is “0.811416” “0.580644” (:2). Any variance lower than (1.0) should be considered ‘good’, since (±1) is actually the smallest-possible, per-result error.


(Updated 12/04/2020, 11h50… )

Continue reading How to compute the sine function, on a CPU with no FPU.

There can be curious gaps, in what some people understand.

One of the concepts which once dominated CGI was, that textures assigned to 3D models needed to include a “Normal-Map”, so that even early in the days of 3D gaming, textured surfaces would seem to have ‘bumps’, and these normal-maps were more significant, than displacement-maps – i.e., height- or depth-maps – because shaders were actually able to compute lighting subtleties more easily, using the normal-maps. But additionally, it was always quite common that ordinary 8x8x8 (R,G,B) texel-formats needed to store the normal-maps, just because images could more-easily be prepared and loaded with that pixel-format. (:1)

The old-fashioned way to code that was, that the 8-bit integer (128) was taken to symbolize (0.0), that (255) was taken to symbolize a maximally positive value, and that the integer (0) was decoded to (-1.0). The reason for this, AFAIK, was the use by the old graphics cards, of the 8-bit integer, as a binary fraction.

In the spirit of recreating that, and, because it’s sometimes still necessary to store an approximation of a normal-vector, using only 32 bits, the code has been offered as follows:

 


Out.Pos_Normal.w = dot(floor(normal * 127.5 + 127.5), float3(1 / 256.0, 1.0, 256.0));

float3 normal = frac(Pos_Normal.w * float3(1.0, 1 / 256.0, 1 / 65536.0)) * 2.0 - 1.0;

 

There’s an obvious problem with this backwards-emulation: It can’t seem to reproduce the value (0.0) for any of the elements of the normal-vector. And then, what some people do is, to throw their arms in the air, and to say: ‘This problem just can’t be solved!’ Well, what about:

 


//  Assumed:
normal = normalize(normal);

Out.Pos_Normal.w = dot(floor(normal * 127.0 + 128.5), float3(1 / 256.0, 1.0, 256.0));

 

A side effect of this will definitely be, that no uncompressed value belonging to the interval [-1.0 .. +1.0] will lead to a compressed series of 8 zeros.

Mind you, because of the way the resulting value was now decoded again, the question of whether zero can actually result, is not as easy to address. And one reason is the fact that, for all the elements except the first, additional bits after the first 8 fractional bits, have not been removed. But that’s just a problem owing to the one-line decoding that was suggested. That could be changed to:

 


float3 normal = floor(Pos_Normal.w * float3(256.0, 1.0, 1 / 256.0));
normal = frac(normal * (1 / 256.0)) * (256.0 / 127.0) - (128.0 / 127.0);

 

Suddenly, the impossible has become possible.

N.B.  I would not use the customized decoder, unless I was also sure, that the input floating-point value, came from my customized encoder. It can easily happen that the shader needs to work with texture images prepared by an external program, and then, because of the way their channel-values get normalized today, I might use this as the decoder:

 


float3 normal = texel.rgb * (255.0 / 128.0) - 1.0;

 

However, if I did, a texel-value of (128) would still be required, to result in a floating-point value of (0.0)

(Updated 5/10/2020, 19h00… )

Continue reading There can be curious gaps, in what some people understand.

Computing Pi

Nowadays, many people take the concept for granted, that they ‘know the meaning’ of certain Mathematical functions and constants, but that if they ever need a numerical equivalent, they can just tap on an actual calculator, or on a computer program that acts as a calculator, to obtain the correct result.

I am one such person, and an example of a Mathematical constant would be (π).

But, in the 1970s it was considered to be a major breakthrough, that Scientists were able to compute (π) to a million decimal places, using a computer.

And so the question sometimes bounces around my head, of what the simplest method might be, to compute it, even though I possess software which can do so, non-transparently to me. This is my concept, of how to do so:

http://dirkmittler.homeip.net/ComputingPi.pdf

http://dirkmittler.homeip.net/Pi_to_5000.pdf

(Update 08/28/2018 : )

The second link above points to a document, the textual contents of which were created simply, using the program ‘Yacas’. I instructed this program to print (π) to 5000 decimal places. Yet, if the reader was ever to count how many decimal places have been printed, he or she would find there are significantly more than 5000. The reason this happens is the fact that when ‘Yacas’ is so instructed, the first 5000 decimal places will be accurate, but will be followed by an uncertain number of decimal places, which are assumed to be inaccurate. This behavior can be thought related, to the fact that numerical precision, is not the same thing as numerical accuracy.

In fact, the answer pointed to in the second link above is accurate to 5000 decimal places, but printed with precision exceeding that number of decimal places.

Dirk

 

Revisiting HTML, this time, With CSS.

When I first taught myself HTML, it was in the 1990s, and not only has the technology advanced, but the philosophy behind Web-design has also changed. The original philosophy was, that the Web-page should only contain the information, and that each Web-browser should define in what style that information should be displayed. But of course, when Cascading Style-Sheets were invented – which in today’s laconic vocabulary are just referred to as “Styles” – they represented a full reversal of that philosophy, since by nature, they control the very appearance of the page, from the server.

My own knowledge of HTML has been somewhat limited. I’ve bought cuspy books about ‘CSS’ as well as about ‘JQuery’, but have never made the effort to read each book from beginning to end. I mainly focused on what some key concepts are, in HTML5 and CSS.

Well recently I’ve become interested in HTML5 and CSS again, and have found, that to buy the Basic license of a WYSIWYG-editor named “BlueGriffon“, proved informative. I do have access to some open-source HTML editors, but find that even if they come as a WYSIWIG-editor, they mainly tend to produce static pages, very similar to what Web-masters were already creating in the 1990s. In the open-source domain, maybe a better example would be “SeaMonkey“. Beyond that, ‘KompoZer‘ can no longer be made to run on up-to-date 64-bit systems, and while “BlueFish”, a pronouncedly KDE-centric solution available from the package-manager, does offer advanced capabilities, it only does so in the form of an IDE.

(Updated 03/09/2018, 17h10 : )

Continue reading Revisiting HTML, this time, With CSS.