Fifty Shades of J/Chapter 24
Table of Contents ... Glossary ... Previous Chapter ... Next Chapter
Principal Topics
- gerund, Balanced rounding
Rounding
Do you feel mildly irritated when a report says something like “the figures may not add up to exactly 100 because of rounding”? I do. For one thing it would probably be just as easy to make the figures add up as to make the excuse, and in any case surely the whole essence of rounding is to make figures tally. You have probably guessed the next bit is going to be “it’s easy in J”, and yes, you are right - moreover it provides a nice illustration of the development of a simple, but not trivially simple, J verb. So let’s begin by breaking down the process of rounding.
Consider the problem of rounding a value to a given number, say n, of decimal places. The simplest approach involves a three stage process. In the first stage the number is raised by moving the decimal point n positions to the right, the second stage consists of swinging the resulting up or down to the nearest integer according to whether the fractional part of the resulting number is above or below 0.5, and the third stage reverses the first stage, that is it lowers the numbers by moving them n positions to the left. “Moving the decimal point” is in turn a process which, in more exact terms, consists of multiplying by 10 to the power n, with positive n meaning move to the right and negative n meaning move to the left. These decimal point movements can be summarised as
pow=: 10&^ NB. 10 to the power raise=: (* pow)~ NB. 1 raise 2.57 is 25.7 lower=: (% pow)~ NB. 1 lower 25.7 is 2.57
Next let’s sharpen the swinging process. Again this is a sequence of two simpler processes, the first consisting of adding 0.5, and the second taking the floor:
swingu=: <.@+&0.5 NB. move to nearest integer swingu 4.4 5.6 2.5 4 6 3
Notice that 2.5 goes up to 3 - more of that later. At first sight the symmetry of the three stage process - raise, swing, lower - might suggest that these three verbs composed as a fork would be appropriate. However maturer consideration shows that this is not the case, since the essential operation of a fork can be summarised informally as : first execute the left and right prongs concurrently, then execute the middle prong on the transformed data, whereas in this case the lowering can only take place after the other two processes have completed, and so raise and lower are not concurrent.
There is in fact a fork present in the rounding process, but it the lower sub-process which forms its central prong, the other prongs consisting of (1) the raising and swinging sub-process in sequence, and (2) the re-extraction of n, the number of decimal places which was “consumed” in the raising sub-process.
This analysis leads to the following development of a rounding algorithm :
rnd=: [ lower swingu@raise NB. syntax is 1 rnd 2.57
The reason for the ‘u’ in swingu is that swinging possesses a degree of asymmetry in that a number with a fractional part which is exactly equal to 0.5 is rounded up. The ‘mirror image’ verb
swingd=: <.@+&0.5 NB. move to nearest integer, 0.5 goes down swingd 4.4 5.6 2.5 4 6 2
has the opposite effect. For most practical purposes the two can be used interchangeably, that is rnd is equivalent to
rndd=: [ lower swingd@raise NB. syntax is 1 rndd 2.57
In the days before computers, the practice was sometimes followed of rounding exact halves to the nearest even integer in the hope that any errors so arising might roughly balance out. A ‘neutral’ swing verb rndn incorporating this can be constructed using a gerund which is J’s mechanism for the case statement.
isodd=: 2&| NB. 1 for an odd integer, 0 for even getfrac=: 1&| NB. Get the fractional part of a number swing=: swingd`swingu @.(isodd&(- getfrac))
If swing is used the (isodd&(- getfrac)) decision has to be made separately for each value in a vector and so the rndn must be written
rndn=: [ lower swing every@raise NB. syntax is 1 rndn 2.57
Now think about how to extend this basic rounding algorithm to do balanced rounding, that is the process of making the rounded values of a vector tally exactly to their rounded total. This problem happens typically with percentages, for example the three values in
a=: 36.24 29.73 34.03 +/ a 100
total exactly 100, but the individual values round to 36.2 29.7 and 34.0 which total 99.9 .
1 rnd a 36.2 29.7 34
Begin by considering what adjustment might sensibly be made in the absence of a calculating device. This would probably be something like: following basic rounding, look for the value whose fractional part after raising comes closest to 0.5 (that is the 36.24) and round that one up. If the deficit between the rounded total and 100 had been 0.2 say, the two values nearest to 0.5 would be rounded up, and so on. Since this procedure happens strictly in the swinging stage, the structure of an algorithm for balanced rounding is going to differ only in one of the verbs already developed for rounding, so write it as
brnd=: [ lower balance@raise NB. Balanced round
The problem is then reduced to that of sharpening what is meant by the verb ‘balance’. Take swingu as a starting point. Instead of adding 0.5 indiscriminately to all the floors in preparation for lowering, it would be better if all raised values were initially truncated (that is floored), and then a value of 1 added to as many as are necessary to fill the gap between the sum of the raised values (1000) and the sum of their floors (999). Call this gap the rounding gap which, translating the previous sentence into J, is (+/) - +/@:<..
Clearly the order of candidature for adding a 1 is that of the size of the fractional part and so a verb must be constructed which determines the ranking of the fractional parts.
Define
getfrac=: 1&| NB. get fractional part rkd=: /:@\: NB. rank a vector downwards rkd 4 2 7 1 NB. eg. 7=max and so has rank 0 1 2 0 3
and compose these two verbs, which is incidentally a nice little illustration of the use of the conjunction bond (&)
(rkd&getfrac) 1 rnd a 1 0 2
This says that, in the present example, the biggest fractional part is associated with the first term. Since the rounding gap is 1, this is the only item to which 1 will be added at the swing stage, and so the result of the comparison rkd&getfrac < calcrgap will supply exactly the right mix of 1s and 0s to add prior to lowering.
For a the rounded total is an integer and so too is the rounding gap. When this is not the case as with
]b=: 1.631 0.478 1.939 4.236 1.631 0.478 1.939 4.236 2 raise b 163.1 47.8 193.9 423.6 +/ 2 raise b 828.4 +/ <. 2 raise b 826
where the rounding gap is 2.4, only two of the items require 1 to be added, whereas if the rounding gap had been 2.6 then the round of the sum would be 8.29 and three of the items would require 1. Thus the rounding gap itself should be swung in order that the balance property be fulfilled that the sum of the rounded values should exactly equal the round of the sum of the original values. This leads to the definition of the verb
calcrgap=: swingu@((+/) - +/@:<.) NB. Calculate rounding gap
and the verb balance completes the operation of adding 1 to qualifying items before lowering
balance=: (rkd&getfrac < calcrgap) + <. NB. adjusted floor
All the elements of brnd are now in place and so its definition is complete.
2 brnd b 1.63 0.48 1.94 4.23 (+/ b),(+/ 2 rnd b),(+/ 2 brnd b) 8.284 8.29 8.28
Finally here is everything brought together to bring this well-rounded article (pun intended!) to a close :
Code Summary
rnd=: [ lower swingu@raise NB. y to x dec.pl, 0.5 rnds up raise=: (* pow)~ NB. multiply y by 10^x pow=: 10&^ NB. 10 to the power y swingu=: <.@+&0.5 NB. adjust y to nrst integer lower=: (% pow)~ NB. divide y by 10^x rndd=: [ lower swingd@raise NB. y to x dpl., 0.5 rnds down swingd=: >.@-&0.5 NB. move to nearest integer rndn=: [ lower swing every@raise NB. 0.5 rnds to nearest even swing=: swingd`swingu @.(isodd&(- getfrac)) NB. gerund isodd=: 2&| NB. 1 for an odd integer, 0 for even brnd=: [ lower balance@raise NB. balanced rounding, OK balance=: (rkd&getfrac < calcrgap) + <. NB. y to nrst integer calcrgap=: swingu@((+/) - +/@:<.) NB. calculate rounding gap getfrac=: 1&| NB. get fractional part of y rkd=: /:@\: NB. rank y downwards