feat: add C implementation for math/base/special/gcd

[aman-095]

Description

This RFC proposes adding C implementation for @stdlib/math/base/special/gcd.

I have implementation ready for C implementation of gcd. There are a few issues associated.

double stdlib_base_gcd( const int32_t a, const int32_t b )

This is the definition I am currently using. The file test.native.js is failing for the following cases:

    the function returns `NaN` if either argument is `NaN`

      ✖ returns NaN
      ✖ returns NaN
      ✖ returns NaN


    the function returns `NaN` if either argument is `+infinity`

      ✖ returns NaN
      ✖ returns NaN
      ✖ returns NaN


    the function returns `NaN` if either argument is `-infinity`

      ✖ returns NaN
      ✖ returns NaN
      ✖ returns NaN


    the function returns `NaN` if either argument is not an integer value

      ✖ returns NaN
      ✖ returns NaN
      ✖ returns NaN


    the function supports providing large integers (>= 2**31 - 1)

      ✖ returns 2**100
      ✖ returns 2**53
      ✖ returns 2**53
      ✖ returns 1
      ✖ returns 8
      ✖ returns 8

Since I am using inputs as two 32-bit signed integers, these will fail as we can't take input as NaN, infinity, and >= 2**31 - 1 cases. So, how should I tackle this issue? Also, the output type I have used is double for the above definition with two 32-bit signed integers as input we won't get any double output including NaN and it will be better to use a 32-bit signed integer for output as well.

To support >= 2**31 - 1 cases, we can have 64-bit signed integers as input and corresponding output of the same type. But for this, I will have to implement the macro that accepts signed 64-bit integers as input and gives the same output. Now, if we need to implement this then what should be the representation for this macro?

napi_value stdlib_math_base_napi_ii_i

This is the representation used for 32-bit integers as input and the corresponding output as a 32-bit integer. 

Related Issues

None.

Questions

No.

Other

No.

Checklist

• I have read and understood the Code of Conduct.
• Searched for existing issues and pull requests.
• The issue name begins with RFC:.

[aman-095]

CC @kgryte @Planeshifter @Pranavchiku

[Pranavchiku]

As per what is discussed at #1661 (comment), you may go ahead with double stdlib_base_gcd( const int64_t a, const int64_t b );.

For macros, I am not sure, you may manually create addon.c without macros for avoid blocker, that can be refactored once we have macros up with us.

[aman-095]

tape( 'the function supports providing large integers (>= 2**31 - 1)', opts, function test( t ) {
	var TWO_100 = 1.2676506002282294e+30;
	var TWO_53 = 9007199254740992;
	var v;

	v = gcd( TWO_100, 0 );
	t.strictEqual( v, TWO_100, 'returns 2**100' );

	v = gcd( 0, TWO_53 );
	t.strictEqual( v, TWO_53, 'returns 2**53' );

	// Verified on Wolfram Alpha:
	v = gcd( TWO_100, TWO_53 );
	t.strictEqual( v, TWO_53, 'returns 2**53' );

	// Verified on Wolfram Alpha:
	v = gcd( TWO_100, 73453 );
	t.strictEqual( v, 1, 'returns 1' );

	// Verified on Wolfram Alpha:
	v = gcd( TWO_100, 3491832 );
	t.strictEqual( v, 8, 'returns 8' );

	// Verified on Wolfram Alpha:
	v = gcd( 3491832, TWO_100 );
	t.strictEqual( v, 8, 'returns 8' );

	t.end();
});

These cases will not work even if we use 64-bit signed integers. If we need to support all these cases then we'll have to use double-precision floating-point numbers as input and the same as output type as well.

[kgryte]

As discussed in #1703, upon further review of the JS GCD implementation, I think the API should be the following:

double stdlib_base_gcd( const double a, const double b )

with essentially the same implementation as JS. This will ensure we can support large exponential numbers, as in JS, and will ensure 1:1 parity between the two implementations.