Jump to content


Photo

GM-GMP - Arbitrary-precision arithmetic library


  • Please log in to reply
14 replies to this topic

#1 Maarten Baert

Maarten Baert

    GMC Member

  • GMC Member
  • 750 posts
  • Version:GM8.1

Posted 30 August 2010 - 07:16 PM

This is a GM port of the GNU Multiple Precision Arithmetic Library. GMP is a library for arbitrary-precision arithmetic, which means doing calculations with numbers with unlimited precision (the precision is only limited by the available memory). I know there was another DLL that did this already (BigInt dll), but this one has far more functions.

So far I've only ported (most of) the integer functions, but I can add more functions on request. The GMP manual can be found here.

Download GM-GMP (source code included)

How it works
I've tried to keep everything as simple as possible, while also making everything as fast as possible. I think that worked out reasonably well, but since everything has to go through GM it will never be as fast as the original GMP library.

The DLL uses strings to represent numbers. I could have used ids or something similar, but that would have been a lot more difficult and it would also introduce memory leaks if you forgot to destroy one of the numbers. That's why I used strings.

Numbers can be stored in several forms. The simplest form is simply decimal, like "1234" for 1234. Negative numbers use a minus sign, like "-1234". Using a plus sign is not allowed, GMP doesn't recognize those. GMP also recognizes other bases, like hexadecimal (with prefix "0x", e.g. "0xf4" = 244), binary (with prefix "0b", e.g. "0b10001101" = 141), octal (with prefix "0", e.g. "0273" = 187). This is how different bases are used in C/C++. You have to be careful with octal though, you should never use leading zeroes. If you want to use a negative number with a different base, the minus sign should come before the prefix (e.g. "-0x12", not "0x-12").

So why is this relevant? Well, since GMP uses binary numbers internally, reading or writing hexadecimal, octal and binary numbers is a lot faster than reading or writing decimal numbers. For that reason all mathematical functions will return hexadecimal numbers. This means you will have to convert them to decimal again, so I've added some conversion functions to do that.

Functions
The functions aren't very hard to use, so I will just give a very brief explanation.

Hints:
  • All mathematical functions return hexadecimal numbers, so use gmp_todec to convert them to decimal.
  • If the results of a calculation are wrong, make sure you are not accidentally passing reals instead of strings to the mathematical functions. All reals will be replaced by empty strings by GM, and empty strings are interpreted as 0 by GMP.

gmp_real(a_string) - This function does exactly the same as real(), but it supports hexadecimal, octal and binary as well, so it can be used to convert the result of mathematical functions to reals. It doesn't support an exponential part though.
gmp_string(a_real) - The same as string(), but better. string() has a very limited range because GM uses a 32-bit integer to store the intermediate result. This function doesn't have this limitation, it will work for any value between -8.9885e307 and 8.9885e307. The result is hexadecimal. This function should be used to convert reals to strings you can pass to the mathematical functions.
gmp_tohex(a_string) - Converts a number (as a string) to hexadecimal. If the number is already hexadecimal, nothing happens. This function will also add the prefix "0x".
gmp_todec(a_string) - Converts a number (as a string) to decimal. If the number is already decimal, nothing happens.

gmp_add(a_string,b_string) - Calculates the sum of two numbers (as strings).
gmp_sub(a_string,b_string) - Calculates the difference of two numbers (as strings).
gmp_mul(a_string,b_string) - Calculates the product of two numbers (as strings).
gmp_div(a_string,b_string) - Calculates the quotient of two numbers (as strings). The result is rounded towards zero, like 'div' in Game Maker.
gmp_mod(a_string,b_string) - Calculates the remainder after division of two numbers (as strings). The result has the same sign as the first number, like 'mod' in Game Maker.
gmp_neg(a_string) - Changes the sign of a number (positive becomes negative, negative becomes positive).
gmp_abs(a_string) - Calculates the absolute value (modulus) of a number (negative becomes positive).

gmp_pow(a_string,n_string) - Calculates a to the power of n. Make sure n is not too big since this would require too much memory.
gmp_powmod(a_string,n_string,mod_string) - Calculates a to the power of n modulo mod.

gmp_sqrt(a_string) - Calculates the square root of a number. The result is rounded towards zero.
gmp_sqrtrem(a_string) - Calculates the remainder of the square root of a number. The result is the same as a-gmp_pow(gmp_sqrt(a),2). If you need both the square root and the remainder, it's probably faster to calculate it yourself to avoid calculating the square root twice.
gmp_root(a_string,n_string) - Calculates the n-th root of a number. The result is rounded towards zero.
gmp_rootrem(a_string,n_string) - Calculates the remainder of the n-th root of a number. See gmp_sqrtrem.

gmp_compare(a_string,b_string) - Compares two numbers. If the return value is positive, a is greater than b. If the return value is negative, a is smaller than b. If the return value is zero, a equals b. This is actually very easy to use: a>=b becomes gmp_compare(a,b)>=0.
gmp_abscompare(a_string,b_string) - Compares the absolute value of two numbers. See previous function.
gmp_sign(a_string) - Returns the sign of a number, like sign() in GM. +1 means positive, -1 means negative, and 0 means zero.
gmp_even(a_string) - Returns whether a number is even.
gmp_odd(a_string) - Returns whether a number is odd.

gmp_probab_prime(a_string,reps) - Returns whether a number is prime. 0 means the number is definitely prime, 1 means the number is probably prime, and 2 means the number is definitely composite (not prime). Increasing the value of reps will reduce the chance of a composite returning 'probably prime'. Usually 10 is a reasonable value.
gmp_probab_nextprime(a_string) - Returns the first prime greater than the given number. The test is not 100% accurate, but the chance of the test being wrong is extremely small.
gmp_gcd(a_string,b_string) - Calculates the greatest common divisor of two numbers.
gmp_lcm(a_string,b_string) - Calculates the least common multiple of two numbers.
gmp_factorial(n_string) - Calculates the factorial of n.
gmp_fibonacci(n_string)- Calculates the n-th Fibonacci number.

gmp_min(a_string,b_string) - Returns the lowest value of two numbers.
gmp_max(a_string,b_string) - Returns the highest value of two numbers.

That's it for now. Good luck!

Edited by Maarten Baert, 23 January 2011 - 04:44 PM.

  • 3
Posted Image

#2 Overpants

Overpants

    GMC Member

  • Banned Users
  • 85 posts

Posted 30 August 2010 - 07:26 PM

I haven't tried it yet but this is really cool. GMP was one of my favorite libraries to use in C++ just 'cause i love seeing big numbers. Nice job!
Current status: NEWEST GAME COMPLETE
Millenium Pants << Download

#3 TheMagicNumber

TheMagicNumber

    GMC Member

  • GMC Member
  • 5247 posts
  • Version:Unknown

Posted 30 August 2010 - 09:14 PM

GM's real doesn't use 32bit integers. That would mean it doesn't support any number with a decimal. It used a double (64bit, double precision floating point). Everything else is great.
  • 0

#4 Overpants

Overpants

    GMC Member

  • Banned Users
  • 85 posts

Posted 30 August 2010 - 09:27 PM

GM's real doesn't use 32bit integers. That would mean it doesn't support any number with a decimal. It used a double (64bit, double precision floating point). Everything else is great.

How is that relevant? The dll takes and returns mostly strings as input. Unless I'm missing your point.
Current status: NEWEST GAME COMPLETE
Millenium Pants << Download

#5 TheMagicNumber

TheMagicNumber

    GMC Member

  • GMC Member
  • 5247 posts
  • Version:Unknown

Posted 30 August 2010 - 09:29 PM

What's the difference between GM's real and this one? This one doesn't support an exponential part, whats the benefit exactly?
  • 0

#6 Maarten Baert

Maarten Baert

    GMC Member

  • GMC Member
  • 750 posts
  • Version:GM8.1

Posted 30 August 2010 - 10:41 PM

What's the difference between GM's real and this one? This one doesn't support an exponential part, whats the benefit exactly?

GM's real() uses a 32-bit int to store the intermediate result. This means things like
a = real("10000000000000000000000000000000000000000");
won't work. gmp_real() supports any number of digits (and even supports hexadecimal, octal and binary), so it can be used to convert the results of the mathematical functions back to reals you can use in GM.

EDIT: Apparently I was wrong, it's only string() that uses a 32-bit int and can't handle anything higher than 2^32-1, real() works just fine. But it doesn't support hexadecimal, octal and binary of course.

Edited by Maarten Baert, 30 August 2010 - 10:49 PM.

  • 0
Posted Image

#7 xot

xot

    GMC Dismember

  • GMC Elder
  • 4785 posts
  • Version:GM:Studio

Posted 30 August 2010 - 11:09 PM

This is a GM port of the GNU Multiple Precision Arithmetic Library.


Shouldn't the DLL include a GPL license and your source code (or a link to it)?
  • 0
GMLscripts.com, rise from your grave!

If any of my posts contain broken images or links, I can probably supply them for you. PM with a link to the post.

#8 Maarten Baert

Maarten Baert

    GMC Member

  • GMC Member
  • 750 posts
  • Version:GM8.1

Posted 31 August 2010 - 10:06 AM

This is a GM port of the GNU Multiple Precision Arithmetic Library.


Shouldn't the DLL include a GPL license and your source code (or a link to it)?

No, GMP uses the Lesser General Public License, which means you can link to the library even if your project is not open source.

I will add the source code anyway :).
  • 0
Posted Image

#9 xot

xot

    GMC Dismember

  • GMC Elder
  • 4785 posts
  • Version:GM:Studio

Posted 01 September 2010 - 02:18 AM

As I understand it, you can link to LGPL code without GPL-ing the code accessing it, but you still need to provide the license to the LGPL code you are accessing. If you have made modifications to LGPL code (you say you ported it), you have to continue to honor the license and provide your source code changes on request.
  • 0
GMLscripts.com, rise from your grave!

If any of my posts contain broken images or links, I can probably supply them for you. PM with a link to the post.

#10 Maarten Baert

Maarten Baert

    GMC Member

  • GMC Member
  • 750 posts
  • Version:GM8.1

Posted 01 September 2010 - 10:43 AM

As I understand it, you can link to LGPL code without GPL-ing the code accessing it, but you still need to provide the license to the LGPL code you are accessing. If you have made modifications to LGPL code (you say you ported it), you have to continue to honor the license and provide your source code changes on request.

I didn't change the code at all, I just created an interface.

GM <--> My code <--> GMP

You can take a look at the source code if you want, I've included it now :).

I don't think I have to include the license just because I'm using a LGPL library. The GCC runtime is LGPL too but I've never seen anyone including the LGPL just because it uses the GCC runtime ...

EDIT: I see what you mean now:

You may convey a Combined Work under terms of your choice that, taken together, effectively do not restrict modification of the portions of the Library contained in the Combined Work and reverse engineering for debugging such modifications, if you also do each of the following:
# a) Give prominent notice with each copy of the Combined Work that the Library is used in it and that the Library and its use are covered by this License.
# b) Accompany the Combined Work with a copy of the GNU GPL and this license document.

But since I'm not 'conveying' the combined work under terms that allow modification (I'm conveying the combined work as a DLL which can't be modified, and I've only included my own source code, not the GMP source code, so that source code is not the combined work), I don't have to do this. They added this to the license to make sure anyone who makes modifications to GMP knows it's actually LGPL-ed, but since you can't make any modifications anyway it doesn't matter.

Edited by Maarten Baert, 01 September 2010 - 10:55 AM.

  • 0
Posted Image

#11 cnk

cnk

    GMC Member

  • New Member
  • 5 posts
  • Version:GM8

Posted 21 August 2012 - 07:49 PM

Could provide some examples with real numbers such as 1,234e-24 ?
Thanks
  • 0

#12 Drara

Drara

    GMC Member

  • GMC Member
  • 325 posts

Posted 21 August 2012 - 09:40 PM

Ohh that is hell of awesome!!
That would enable Diffie–Hellman key exchanging or even RSA encryption in GM!! ...now I'd only need to find a situation where that would be useful... xD

Edited by Drara, 21 August 2012 - 11:37 PM.

  • 0

#13 Mayhem Games

Mayhem Games

    Proud Kiwi

  • GMC Member
  • 959 posts
  • Version:GM:Studio

Posted 06 September 2012 - 06:46 AM

Ohh that is hell of awesome!!That would enable Diffie–Hellman key exchanging or even RSA encryption in GM!! ...now I'd only need to find a situation where that would be useful... xD

You can already do both of those encryptions in Game Maker, Diffie Hellman especially. This would only allow them to be done more efficiently.
  • 0

For a long time it puzzled me how something so expensive, so leading edge, could be so useless, and then it occurred to me that a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are, in short, a dangerously perfect match. ~ Bill Bryson


#14 Drara

Drara

    GMC Member

  • GMC Member
  • 325 posts

Posted 06 September 2012 - 03:14 PM

Ohh that is hell of awesome!!That would enable Diffie–Hellman key exchanging or even RSA encryption in GM!! ...now I'd only need to find a situation where that would be useful... xD

You can already do both of those encryptions in Game Maker, Diffie Hellman especially. This would only allow them to be done more efficiently.

Well theoretically it'd be possible but it would be not secure. To be secure against an attack you need to use numbers with several dozens length and that's not possible in GM alone..
  • 0

#15 Mark Ian

Mark Ian

    GMC Member

  • GMC Member
  • 137 posts
  • Version:Unknown

Posted 13 September 2012 - 02:27 PM

nice, this will work great for my particle simulations. Thanks
  • 0
That Obscure Object of Desire