GNU BC: "modulo" % with scale other than 0

Question

If the scale is other than zero, calculations with %, such as 3%2 and 46%4, tend to output 0. How is the algorithm designed with the scale other than 0?

bc
scale=10
print 4%3   // output 0

Answer 1

The command manual says this about how BC calculates the modulo:

The result of the expression is the "remainder" and it is computed in the following way. To compute a%b, first a/b is computed to scale digits. That result is used to compute a - ( a/b ) * b to the scale of the maximum of scale+scale(b) and scale(a). If scale is set to zero and both expressions are integers this expression is the integer remainder function.

---

EDIT: I looked at the source code for GNU BC and found that the mod operator extends the division operator. In other words, the modulo is calculated as a by-product of the division. It relies on integer division to calculate the modulo. When scale is set, however integer division does not take place.

Try this in BC:

bc
scale = 0
print 5/2

scale = 5
print 5/2

you should get:

2        << Integer Division
2.50000  << NOT integer division!

Now let's plug in these figures the way BC does. The manual says it uses a-(a/b)*b to calculate. Let's plug in our two results, the one resulting from integer division and the one with a scale other than 0.

a - ( a/b ) * b
5 - ( 2   ) * 2  = 1  << CORRECT!
5 - ( 2.5 ) * 2  = 0  << VERY WRONG!

Without integer division:

a - ( a/b ) * b == a - (  a  ) == 0

This is why scale must be set to 0 for the modulo to work properly.
The issue seems to arise out of the design of BC and how it handles numbers with a 'scale'. In order for the modulo to work correctly we need integer division.

There are other much more advanced tools that are free and open source for this purpose, and I recommend you use them.

Answer 2

I solved it this way:

integer

define int(x) { oldscale=scale; scale=0; x=x/1; scale=oldscale; return( x ); }

modulo

define mod(x,y) { oldscale=scale; scale=1000; x = x - y * int(x/y); scale=oldscale; return( x ); }

HTH

Answer 3

user272970's answer is great. Here's a tweak to it:

define int(x) { auto oldscale; oldscale=scale; scale=0; x=x/1; scale=oldscale; return( x ); }
define fmod(x,y) { auto oldscale; oldscale=scale; scale=1000; x = x - y * int(x/y); scale=oldscale; return( x ); }

This (using auto oldscale) makes oldscale local to the function. Without that, setting oldscale in int() from fmod() will overwrite the oldscale that is trying to be saved in fmod(), leaving scale set to 1000 instead of whatever you had before calling fmod().

I added these functions to ~/.bcrc and set the BC_ENV_ARGS environment variable to ~/.bcrc. That will load these functions every time you run bc. So now I can just run fmod(x,y) any time I'm in bc without having to manually define those functions every time.

p.s. scale of 1000 might be overkill in most cases

Answer 4

The % operator is clearly defined in the bc manual as ^[a] :

# Internal % operator definition:
define internalmod(n,d,s) { auto r,oldscale;
                            oldscale=scale; r=n/d;
                            s=max(s+scale(d),scale(n)); 
                            scale=s; r = n-(r)*d;
                            scale=oldscale; return(r) }

Assuming max has been defined as:

define max(x,y){ if(x>y){return(x)};return(y) }

How is that long definition useful?

1. Integer remainder.
I'll use both the internalmod function and the % operator to show they are equivalent for some operations below

If the numbers are integer, and scale is set to 0, it is the integer remainder function.

$ bc <<<'n=17; d=3; scale=0; a=internalmod(n,d,scale); b=n%d; print a," ",b,"\n"'
2 2
$ bc <<<'n=17; d=6; scale=0; a=internalmod(n,d,scale); b=n%d; print a," ",b,"\n"'
5 5

That is not the same as the math mod function. I'll solve that below.

2. Decimal remainder.
If the number n is a longer decimal number, and we modify the scale, we get:

$ bc <<<'n=17.123456789;d=1; scale=0 ;a=internalmod(n,d,scale);b=n%d;print a," ",b,"\n"'
.123456789 .123456789

$ bc <<<'n=17.123456789;d=1; scale=3 ;a=internalmod(n,d,scale);b=n%d;print a," ",b,"\n"'
.000456789 .000456789

Note that here, the first 3 decimal digits were removed and the remainder given is from the fourth decimal digit.

$ bc <<<'n=17.123456789;d=1; scale=7 ;a=internalmod(n,d,scale);b=n%d;print a," ",b,"\n"'
.000000089 .000000089

That shows that the remainder is made more versatile by that definition.

3. Scale change The change of scale is required because the number d (divisor) may have more decimal digits than n. In that case, more decimals are needed to have a more precise result from the division:

$ bc <<<'n=17.123456789; d=1.00000000001; scale=0; a=internalmod(n,d,scale);
         b=n%d; print a," ",scale(a)," -- ", b," ",scale(b),"\n"'
.12345678883 11 -- .12345678883 11

And, if the scale change:

$ bc <<<'n=17.123456789; d=1.00000000001; scale=5; a=internalmod(n,d,scale);
         b=n%d; print a," ",scale(a)," -- ", b," ",scale(b),"\n"'
.0000067888287655 16 -- .0000067888287655 16

As can be seen above, the scale value expands to present a reasonably precise result of the division for any value of n, d and scale.

I'll assume that by the comparison between the internalmod and the % operator both have been proven to be equivalent.

4. Confusion. Be careful because playing with the value of d may become confusing:

$ bc <<<'n=17.123456789; d=10; scale=3; a=n%d; print a," ",scale(a),"\n"'
.003456789 9

And:

$ bc <<<'n=17.123456789; d=1000; scale=3; a=n%d; print a," ",scale(a),"\n"'
.123456789 9

That is: the value of d (above 1) will modify the effect of the value of scale set.

Probably, for values of d different than 1 you should use scale=0 (unless you really know what you are doing).

5. Math mod.
Since we are taking such a deep dive into mod functions, we probably should clarify the real effect of % in bc. The % operator in bc is using a "truncating division". One that rounds toward 0. That is important for negative values of both n and/or d:

$ bc <<<'scale=0; n=13; d=7; n%d; '
6

$ bc <<<'scale=0; n=13; d=-7; n%d; '
6

The sign of the remainder follows the sign of the dividend.

$ bc <<<'scale=0; n=-13; d=7; n%d; '
-6

$ bc <<<'scale=0; n=-13; d=-7; n%d; '
-6

While a correct math mod should give an always positive remainder.

To get that (integer) mod function, use:

# Module with an always positive remainder (euclid division).
define modeuclid(x,div)  {  if(div!=int(div)){
                            "error: divisor should be an integer ";return(0)};
                            return(x - div*int(x/div))  }

And this will work:

$ bc <<<"n=7.123456789; d=5; modeuclid(34.123456789,7)"
6.123456789

---

^[a]

expr % expr
The result of the expression is the "remainder" and it is computed in the following way. To compute a%b, first a/b is computed to scale digits. That result is used to compute a-(a/b)*b to the scale of the maximum of scale+scale(b) and scale(a).
If scale is set to zero and both expressions are integers this expression is the integer remainder function.

---

For the bc code that follows the point where this footnote was introduced to work correctly, define an alias as:

$ alias bc='bc -l "$HOME/.func.bc"'

And create a file named $HOME/.func.bc that contains (at least):

# Internal % operator definition:
define internalmod(n,d,s) { auto r,oldscale;
                            oldscale=scale; r=n/d;
                            s=max(s+scale(d),scale(n)); 
                            scale=s; r = n-(r)*d;
                            scale=oldscale; return(r) } 
# Max function
define max(x,y){ if(x>y){return(x)};return(y) }

# Integer part of a number toward 0:  -1.99 -> -1, 0.99 -> 0
define int(x)        {  auto os;os=scale;scale=0;
                        x=sgn(x)*abs(x)/1;scale=os;return(x)  }

define sgn (x)       {  if (x<0){x=-1};if(x>0){x=1};return(x) };
define abs (x)       {  if (x<0) x=-x; return x }; 

# Module with an always positive remainder (euclid division).
define modeuclid(x,div)  {  if(div!=int(div)){
                            "error: divisor should be an integer ";return(0)};
                            return(x - div*int(x/div))  }

---

A mod function for any number (integer or not) may be defined as:

# Module with an always positive remainder (Euclid division).
define modeuclid(x,div)  {  div=abs(div);return(x - div*floor(x/div))  }

# Round down to integer below x (toward -inf).
define floor (x)         {  auto os,y;os=scale;scale=0;
            y=x/1;if(y>x){y-=1};scale=os;return(y) };

This definition is perfectly valid and correct by math rules, however, it may become quite confusing when trying to apply it in real cases, just saying.

Answer 5

As other answer have said, it's the result of defining a%b as (a-(a/b)*b), evaluated at the current scale. This means that if you want it to act as an integer modulus, you need to use it with scale=0.

However, I disagree that it is "wrong". It is a potentially useful tool, especially for evaluating error.

scale=5
1/3
> .33333
1%3
> .00001

What are we losing if we represent 7/13 as the 4-digit decimal .5384?

scale=4
7/13
> .5384
7%13
> .0008

Apparently 0.0008/13.

And lastly, because it doesn't insist on using integers, it can be used to extract a portion of a decimal.

scale=1
123.456/1
> 123.4
123.456%1
> .056