Unusual Floating-Point Format Remembered?

Herman Rubin wrote: > In article , > Jerry Avins wrote: >> [...] >

The C99 mixed format with hex mantissa and decimal radix two powers works pretty well for the latter situation, if I understand your point correctly.

-- David

In article , snipped-for-privacy@odds.stat.purdue.edu (Herman Rubin) writes: |> |> You rarely do well by microcontrolling roundoff, but |> it is necessary to control it. My crude estimate of |> the precision needed to carry out Remez' Second Algorith |> (one of the best for getting uniform approximations of |> functions) is at least triple the precision wanted, and |> this must be taken into account in the calculations, |> including solutions of linear equations. |> |> In fact, things can be worse. Consider getting the |> convolution of the sequence 1/j!, j=0,...,127 by the |> fast Fourier transform.

Indeed. Or calculating sum(1/i, i = 1,n)-log(n), which is perhaps the simplest calculation where probabilistic rounding is the only game in town.

|> Floating point roundoff can be catastrophic, as can |> fixed point, or anything other than integer or fixed |> point rational.

However, you are talking about issues at least two (decimal) orders of magnitude more numerically advanced than simply generating closed ellipses on a discrete plotter!

In a case like that, you don't need to even KNOW the base, rounding or integer conversion rule. The obvious code is independent of all of them, as I am sure you know.

Regards, Nick Maclaren.

In article , Jerry Avins writes: |> |> However slow integer division might be on a particular machine, getting |> the remainder takes no extra time. Most high-level languages discard it, |> but it is there. I know the technique of scaling so that only the |> integer part is needed as "fixed point". Division has remainders |> nevertheless.

On the machines you have come across, perhaps. Not on all, not even on all modern ones. Quite a few RISC CPUs don't even HAVE integer division hardware in hardware (and sometimes not even multiplication). And many of those that emulate it or use the floating-point unit for integer multiplication or division DON'T have the specification you expect.

|> Maybe I don't understand what you mean. If you scale all your quantities |> so that only the integer part is relevant, why use floating point at all?

Simplicity. If you use integers, you have to emulate floating-point (or at least fixed-point). Because this is getting nowhere, here is a rough draft of the code that is independent of base, rounding rule and integer conversion rule. All that is required of the latter two is that the rounding is half-sane and the integer conversion is consistent (e.g. up, down or nearest - though 90% would be fine, too).

For a plotter with N steps, and an arbitrary ellipse, generate the affine transformation to create the ellipse from the unit circle (in floating point, scaled to N). Generate a suitable number of steps, K, and eps = 2pi/K to get better than unit step precision.

x = (0.0,1.0) FOR i = 0...k x = x+eps*(x[1],-x[2]) y = affine(x) z = integer_part(y[1],y[2]) IF z is same as last time THEN loop

There are numerous specialisations and optimisations. Yes, that really does Just Work, assuming that I haven't inserted a stupid mistake after all these years. You don't even need to KNOW any of the properties of the floating-point, except that there must be enough precision; the same code works with NO changes on any system that isn't hopelessly broken.

It really IS that simple.

Regards, Nick Maclaren.

I trust you that it is that simple in practice. The integer arithmetic we used, including transcendentals, provably closed regardless of of how round-offs accumulated. That helpes when we needed the rest of the company to trust us.

Jerry

--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

...

Our issue was not the closure of any one ellipse, but the closure of an entire mask consisting of hundreds of arbitrarily places patterns, laid down in whatever order seemed sensible to the IC designer. That too is orders of magnitude more complex.

Jerry

--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

In that case, I see the advantage of decimal arithmetic, and even decimal floating-point.

The IC designers will specify their dimensions as finite decimal numbers, but you may not know in advance the maximum precision or the scaling they will use.

And they're specifying the layout of at least *some* parts of the design not as coordinates of points, but as vectors?

Or perhaps you are using a plotter that needs its input as vectors? In that case, though, closure doesn't need decimal floating-point, and is more likely to be a mechanical problem of the plotter design. Oooh! Oooh! Maybe you're using an electrostatic plotter, but because of the kind of pattern you're drawing, you're using it in a mode that simulates a pen plotter.

Yes, then you *do* need to have a method to ensure that, almost all of the time, a column of messy figures put in will add up exactly with no rounding whatever. And DFP, if it happens to be handy, will do as well as more elegant methods that require more rewriting of code that worked well on your old computer.

John Savard

We initially used decimal floating point. We went to binary integer when that was no longer available.

Commercial ICs were in their infancy when we did this work. Much of the

4000 series CMOS logic and some of the contemporary analog circuitry was laid out in Gerber #2.

The plotter's input was via punched paper tape using a language called "APT", a popular numerically-controlled machine language at the time. Our program on the mainframe took input on punch cards and produced the paper tape.

We were sorry to lose DFP, and made do with integer.

Jerry

--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Did you mean "x = x+eps*(-x[2],x[1])" ? :-)

Why does x trace a circle instead of a spiral ?

--
pa at panix dot com

My gut reaction, based on my experience and training in these matters, is that an application such as yours should have been programmed in integer in the first place.

Assuming floating-point numbers have certain arithmetic properties - even if they happen to have these properties _on the particular machine you're using_, because it has decimal arithmetic - is bad, because it leads to programs that have to be rewritten when they are transported to other machines.

If you need arithmetic on exact multiples of some value, you use integers scaled to that value, whether it is 1/16,384, 0.00001, or

1/16,807. Because integers can perform exact arithmetic in multiples of 1. Floating-point *might* let you use exact arithmetic in multiples of 1/16,384 on a binary machine, 0.00001 on a decimal machine, and 1/16,807 on a machine using base-7 arithmetic (16,807 = 7^5), but that's an assumption one is not entitled to make.

Floating point is to be used where an approximation to the real number line is required. It has a certain exponent range, and a certain precision, on any given machine, and one does have to take those properties into account. It is intended for applications relating to things like physical quantities, where computations meeting a certain error criterion are satisfactory - where that error criterion is stated as a maximum percentage error on each multiplication and division, and a maximum percentage of the larger (in magnitude) input argument for addition and subtraction. With no specification of when that error takes place, and where the points where the error can be zero may be located. The only allowable cheat is to note that floating- point arithmetic will allow exact integer arithmetic within a limited range (but without any notice of "overflows" beyond that range that provide less-than-integer precision in later integer results).

This viewpoint was drilled into people because it was appropriate for the kind of hardware that was available, and the computing environment in which people would have to make do with whatever computer happened to be the mainframe on the campus they might be studying at, working at, or visitiing. Not to mention being able to share one's FORTRAN code with other researchers.

The fact that today we have a standard for binary floating-point, IEEE

754, which mandates very high-quality numeric behavior, and which has been widely implemented, to the extent of modified versions of Goldschmidt division being developed, used (and patented) that provide the required exact nearest result from division already means that the old days of coding everything for the lowest common denominator of floating-point are passing. But with binary floating-point, the fact still remained that programmers had no more right to assume that 0.0001 would be exact than they had to assume that 1/16,807 would have an exact representation.

Assuming that (a+b)/2.0 is always somewhere in the interval [a,b] works for floating-point when the radix is less than 4. Making such an assumption, in the old days, would have been _just as bad_ as assuming that 0.0001 is exact; both assumptions would have been false on a System/360, having radix-16 floating-point. IEEE 754 binary floating point, though, does not break the former; and DFP would not break the latter.

If one were to argue against DFP because it encourages "sloppy" programming, I suppose one could argue against IEEE 754 because it does the same thing. Perhaps Nick Maclaren's statements that he is _not_ opposed to decimal floating point _per se_ are because he has considered this very issue, and sees the illogic in opposing something new _merely_ because it allows programmers to ignore rules which were once important for them to obey in a past, messier, environment.

But it is also correct to worry that DFP, once widely implemented, might be used unwisely on occasion. Some programmers might specify DFP because they think, hey, it gives nicer results on some obvious occasions, and it's just as good, isn't it, so it's better in every way... and then have programs fall apart that were written assuming floating-point numbers share some properties with the real numbers that IEEE 754 binary does, and DFP doesn't, such as the example quoted above from one of Nick Maclaren's posts.

As long as DFP isn't implemented with such energy that it tempts microprocessor designers to drop IEEE 754 binary support, as long as it stays an orphan format used only for non-compute-bound problems, and so it doesn't get a Wallace tree multiplier of its own, though, I can't get excited about the consequences. With or without DFP, numerical programs written by rank amateurs will give wrong answers; not even IEEE 754 binary can prevent that.

Since the number of transistors on a chip keeps growing, but yet will never be infinite, though, I can't guarantee what tradeoffs will make sense to chip designers in years to come.

And, therefore, I've noted how one could make DFP nicer, by coding in an extra appended digit which is sometimes just 0, sometimes 0 or 5, sometimes 0, 2, 4, 6, or 8, so that precision gets lost on the tail end by smaller steps: by a factor of at most 2.5. Numerically nice DFP. Unlike emulating IEEE 754 binary, this is something relatively easy to do on a machine with only DFP support.

However, this only addresses the particular example raised by Nick Maclaren, and it's entirely possible it would still lose other important properties of IEEE 754 binary that would affect real-world programs using floating-point that were written with reasonable caution. Much closer examination than I would be competent to supply would be needed to determine if this idea is genuinely useful. If it is, it's somewhat of a pity that I hadn't thought of it sooner, because it would then have been helpful to have it as a part of the DFP standards from the very beginning. But since dropping binary floating-point support is a distant prospect in any case, if it is even a possibility, it should be no big deal.

John Savard

We did figure that out. The year was 1964; our mainframe, an RCA clone of some IBM version, had less than a megabyte of core.

I was an analog designer and a novice Fortran programmer; maintaining the Gerber was my introduction to digital logic. (Find the card with the bad flip-flop -- two per card -- repair it if no spare was available.)

[snip excellent summary that I wish all people who write programs knew]

...

Reading your proposal was my entry to this thread. I think it's neat and clever, but I'm not sure of its importance, especially of its importance in the embedded world where humans won't likely see the numbers.

Binary numbers bother some people in the same way that RPN bothers other people, and Arabic numerals -- they were outlawed for a time -- once bothered others. I think the issue is not as important as learning when to use [2c/sqrt(b^2 - 4ac)] instead of [sqrt(b^2 - 4ac)]/2a. Too few programmers realize that most implementations of IEEE 745 have perils for real-time applications because of the excessive time that denorms consume.

Jerry

--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

If it was a clone of the 360/20, it would have had 32 kilobytes of core or less.

But larger mainframes still made floating-point an *option*, although I don't believe a FORTRAN using software decimal floating-point for machines with the commercial instruction set option only existed for them; the only case I know of is the Univac 9200 and 9300.

John Savard

A Megabyte in 1964? Really? I don't believe IBM allowed a Megabyte (physical) until the 3165 in '70ish.

Binary numbers had better not bother anyone working in technical fields.

--
  Keith

Did I say a megabyte? Did you miss *less*?

...

We evidently agree there.

Jerry

--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

It was, as I remember, a model or two before the Spectra 70, but I don't remember the model. It was RCA's clone of an IBM machine. I had decimal floating point, so some IBM machine must have had it too.

Jerry

--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

No, but SIX years later the MAXIMUM was 1MB. Did you miss that? I doubt you had 32KB in '64.

--
  Keith

..

I thought we had 32 Kwords in 64. I remember we got the second megabyte around 1972.

Jerry

--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

(snip)

I knew of a 360/91 with 2MB, I believe in 1969.

That is 16 way interleaved 750ns real magnetic core.

-- glen

An early advertising brochure for the RCA Spectra 70 series dates from

1965, and the first edition of the manual for the RCA Spectra 70 models 45 and 55 is dated June 1965.

In the advertising brochure, we find that the maximum memory capacities of the various Spectra 70 models were:

System 70/15: 8,192 bytes System 70/25: 65,536 bytes System 70/45: 262,144 bytes System 70/55: 524,288 bytes

So, indeed, he would have had less than a megabyte even on the top of the line Spectra 70 machine.

Of course, he is now stating that he was using a machine which was a clone of a decimal IBM machine which preceded the System/360. I'm not aware of such a machine offhand.

As for IBM, the original 1964 edition of IBM System Summary, Form No. A22-6810-0, gives the following information:

Model 30: 65,536 bytes Model 40: 262,144 bytes Model 50: 262,144 bytes Model 60 and 62: 524,288 bytes Model 70: 524,288 bytes

Of course, by the time of actual shipment, models 60 and 62 were replaced by model 65, and model 70 was replaced by model 75.

Even then, however, slower (8 microsecond) core was advertised which came in blocks of 1 or 2 megabytes, which allowed 8 megabytes of bulk core on models 50 and above.

If we now advance to the thirteenth edition of the system summary, from 1974, again available from Al Kossow's site, we have the following maximum main memory capacities for System/360 models then extant (the 1 or 2 megabyte bulk core is given a model number, 2361, so it was a real product):

Model 22: 32,768 bytes Model 25: 49,152 bytes Model 30: 65,536 bytes Model 40: 262,144 bytes Model 50: 524,288 bytes Model 65 and 67: 1,048,576 bytes (twice that is available in a dual-processor system) Model 75: 1,048,576 bytes Model 195: 4,194,304 bytes

The System/360 Model 195 was announced in 1969 but first shipped in

1971 with a possible 4 megabyte storage capability. It combined cache with pipelining, somewhat like today's Pentium microprocessor.

The one-megabyte storage capacity was available for Model 67 at least as early as 1967. Also, System/360 Model 91, shipped in 1967, was available with memory of up to 4,194,304 bytes at that time.

John Savard

I forgot the '91. Ok, so I was a year off. 1MB was a *lot* of doughnuts in '64.

--
  Keith