Big problem with fp plugin and Integer divide

Just calling attention

No actually not, my background us not math. So all advises from you math guys is the only way we can fix math problems u-in this plugin.

I can fix structural issues and other such but not the math.

1 Like

So his modulus ends here

void myModulus(mb& z, const mb& x, const mb& n)
{
	static mb		temp, nn;
	static bool		initGood=false;
		
	if(!initGood)
	{
		init(temp);
		initGood = true;
	}
	
	if(!n.n)
		return;
	
	if(!x.n)
	{
		z.n = 0;
		return;
	}
	
	nn = abs(n);
	
	divRem(temp, z, x, nn);
	
	if(x.n<0 && nn.n>0)
		add(z, z, nn);
	
	if(z>nn/2)
		z = z - nn;
	 
	/*
	if(z==nn)
		z = 0;
     */
		
}/* myModulus */

Original idea was to just apply the workaround like this

void myModulus(mb& z, const mb& x, const mb& n)
{
	static mb		temp, nn;
	static bool		initGood=false;
		
	if(!initGood)
	{
		init(temp);
		initGood = true;
	}
	
	if(!n.n)
		return;
	
	if(!x.n)
	{
		z.n = 0;
		return;
	}
	
	nn = abs(n);
	
	divRem(temp, z, x, nn);
	
	if(x.n<0 && nn.n>0)
		add(z, z, nn);
	
	if(z>nn/2)
		z = z - nn;

	if (z < mb(0.0))
	{
		z = z + n;
	}
	 
	/*
	if(z==nn)
		z = 0;
     */
		
}/* myModulus */

What Robert discovered:

That means that for a “r = x mod y” when x is 5 to 9 and y = 10, when r is negative, add y to fix it ok?

But… what happens when y <> 10?

And using the original workaround rule, the things get broken, for example, for x=-11 and y=-5 if returning the correct r=-1, triggering the rule, and adding y, and instead of -1 we could end with -6

That was my worrying. A set of tests must be done after implementation.

My test so far was on 11 mod 3 I think it was.

But I guess large random set could be generated in code with Xojo integer and one could execute Xojo mod on it, and then feed same set to the BigInteger and let it check if we get same value

That’s a good idea. You must assure diverse positives and negatives x and y.

As Rick surmised, if the result is negative it’s probably necessary to add back the modulus value, not the fixed value 10. But better to find the reason why it’s happening in the first place if possible, and fix it at the source.

It would help to have the definition of mb& (which I assume is the bigInteger data structure or class) and also the code for divRem(). I’ve done almost no programming in C syntax languages, so it’s a slow process for me to read the code, but I’d be happy to poke through it.

Should also note that there appears to be some difference of opinion about how to handle the sign of the result if either or both of the operands are negative. I believe Xojo’s standard mod operator handles it differently than Excel’s mod function. In any event, if both operands are positive, the result should always be positive.

The code is not exactly nice to go through, not exactly normal c coding styles, here is divRem.

The mb class is huge, probably easier to view that on our repo than here.

// z = x/y with remainder; assume x and y are normalized
// if abs(y.n) = 1 we do short division, else INT32 division
bool divRem(mb& z, mb& rem, const mb& x, const mb& y)
{
	mb			xt, yt, zt;
	
	if(!y.n)
		return false;
	
	if(!x.n)
	{
		z.n = 0;
		rem.n = 0;
		return true;
	}
	
	equate(xt, x);
	equate(yt, y);
	
	if(abs(y.n)==1)
	{
		rem.n = 1;
		update(rem);
		rem.b[0] = mbShortDiv(z, xt, yt);
		if(!rem.b[0])
			rem.n = 0;
		if(xt.n<0)
			rem.n = -abs(rem.n);
		return true;
	}
	
	if(!div(z, xt, yt))
	{
		z.n = 0;
		rem.n = 0;
		return false;
	}
	
	equate(zt, z);
	
	mul(rem, zt, yt);
	sub(rem, xt, rem);
	
	mbNormalize(rem);
	
	return true;
	
}/* divRem */

Here is my algorithm for mod after pondering a bit about it:


// r = mod(x, y)  -->

If x = NaN or y = NaN Then   return NaN

If y = 0 Then   return NaN

If x = 0 Then   return 0

Var  ay = abs(y)
Var  minusdiv = -( abs(x) / ay)

If x > 0 and y > 0  then  return ( x + ay * ceil(minusdiv)  )

If x < 0 and y < 0 then return ( x – ay * ceil(minusdiv) )

If y < 0 then return ( x + ay * floor(minusdiv) )   // x > 0 and y < 0

return ( x – ay * floor(minusdiv) )   // x < 0 nd y > 0

Both floating and integer algorithms as Xojo functions:

Public Function fMod(x As Double, y As Double) As Double
  // r = mod(x, y)  -->
  
  If x.IsNotANumber or  y.IsNotANumber Then   return Sqrt(-1) // Nan
  
  If y = 0 Then   return Sqrt(-1) // Nan
  
  If x = 0 Then   return 0
  
  Var  ay As Double = abs(y)
  Var  minusdiv As Double = -( abs(x) / ay)
  
  If x > 0 and y > 0  then  return ( x + ay * ceiling(minusdiv)  )
  
  If x < 0 and y < 0 then return ( x - ay * ceiling(minusdiv)  )
  
  If y < 0 then return ( x + ay * floor(minusdiv) )   // x > 0 and y < 0
  
  return ( x - ay * floor(minusdiv) )   // x < 0 nd y > 0
  
End Function


Public Function iMod(x As Int64, y As Int64) As Int64
  // i = mod(x, y)  -->
  
  // Integer mod
  
  If y = 0 Then Return 0
  
  Var t As int64 = x / y   // gets quotient
  t = t * y                // multiple of y nearest to x 
  
  Return (x - t)  // remainder
  
End Function

I dont know why his BigInteger mod is so complex…in theory it should be just like the Int64 one you put above.

Though yours does not handle if either x or y is negative I suppose…

I did few tests with my algorithms, couldn’t find fails ( yet :smiley: , I’ll let others to find any ) for any mix of positive and negatives.

But right now I’ll let you, Robert and others go beyond exploring the C code.

You could add this precondition as well

If y = 1 Then   return 0
1 Like

I’m looking at the repo now, but there are a lot of files and I’m not sure which source file the mb definition is in. Could you point me to the correct file? Thanks.

Its in mb.h and mb.cpp

Oops, I guess that should have been obvious, but I never noticed those file names. Thanks. I’ll have a look through them.

At once:

If x = 0 or y = 1 Then   return 0