Recent

Author Topic: MathEx, a proposal  (Read 7501 times)

CuriousKit

  • Jr. Member
  • **
  • Posts: 78
MathEx, a proposal
« on: October 03, 2017, 11:12:06 pm »
Hi everyone.

I started doing some development on advanced mathematical functions, mostly to aid in number theory-centric operations (think, for example, searching for prime factors in large numbers akin to GIMPS) but also to develop some highly optimised vector processing commands for games (e.g. multiplying an array of 4-component vectors by a 4x4 matrix).

This is not meant to replace the gmp library, but complement it, in that while gmp is designed for extremely large or arbitrary-precision numbers, what I'm developing is for handing a large number of operations on smaller numbers simultaneously.  For example, using SSE and 16-bit integers, calculate the remainders when a number is divided by 8 different prime numbers, as well as a fast and parallel "MulMod" operation (used when factors have distinct forms, such as k.2n+2 for Fermat factors, in which 2n+2 mod p can be pre-calculated (n may be quite large), then combined with k mod n afterwards).

Currently I can only write optimised code for x86 and x86-64 on Windows, but I'm structuring it so it can be extended for other platforms, and there's a Pascal fallback should such an optimisation not exist for a particular platform.

Before I get too deep into it, does such a library already exist, and if not, would people be interested in seeing such a library? And what functions would be useful, where both speed and correctness are a must?

P.S. Suggestions for a better name would be very welcome too!

Phil

  • Hero Member
  • *****
  • Posts: 2737
Re: MathEx, a proposal
« Reply #1 on: October 04, 2017, 06:09:36 pm »
Before I get too deep into it, does such a library already exist, and if not, would people be interested in seeing such a library? And what functions would be useful, where both speed and correctness are a must?

P.S. Suggestions for a better name would be very welcome too!

What you describe sounds very specialized and I wouldn't be surprised if there was no one else here familiar with what you're doing. But don't let that deter you from developing a bang-up, general-purpose library that meets your needs. In general, I've always found that writing code as though someone else will be using it is a great motivator to go that extra distance and really make the code shine. Note that support for non-Windows platforms would be essential.

I think the community here is really a lot smaller than some think it is. There are quite a few hobbyists and novices, but perhaps not so many of the kinds of professionals that might be doing something like what you're interested in.


CuriousKit

  • Jr. Member
  • **
  • Posts: 78
Re: MathEx, a proposal
« Reply #2 on: October 04, 2017, 08:23:41 pm »
Aww, that is a shame.  Still, as you said, I won't let it deter me.  I like to think that the vector and matrix functions will at least find a use!  True, the functions for doing modular arithmetic are very much specialised for number theory.  I guess part of me wants to encourage the community to grow if there are suitable libraries for scientific, gaming and financial purposes, for example.  I want to put my knowledge of mathematics to good use!

I don't have much access currently to non-Windows platforms, and probably won't do for a while, but I still intend to provide support - at the very least I intend to provide Pascal fallback code for everything.  Linux code (it has different rules to Windows where procedure calling is concerned) shouldn't be too hard to implement once I get more comfortable with it.
« Last Edit: October 04, 2017, 08:25:56 pm by CuriousKit »

mas steindorff

  • Hero Member
  • *****
  • Posts: 532
Re: MathEx, a proposal
« Reply #3 on: October 04, 2017, 08:58:25 pm »
do a search on math and or matrix in this forum, I was reading something a few days ago about the speed of a 1000x1000 multiply.  someone has integrated a forth DLL  that also uses selected CPU features.
windows 10 &11, Ubuntu 21+ - fpc 3.0.4, IDE 2.0 general releases

Phil

  • Hero Member
  • *****
  • Posts: 2737
Re: MathEx, a proposal
« Reply #4 on: October 04, 2017, 09:27:31 pm »
I don't have much access currently to non-Windows platforms, and probably won't do for a while

Try VirtualPC. That's what I use on my Mac, with Ubuntu installed in it, for testing FPC on Linux.

If you want something even easier, so you don't even have to install Linux, try a free 1-year AWS account. Then you'll also have a real Linux server environment if you need that for anything:

https://macpgmr.github.io/MacXPlatform/PascalDynLibs_4.html

Edit: Oops, meant VirtualBox, not VirtualPC.
« Last Edit: October 04, 2017, 11:16:14 pm by Phil »

hrayon

  • Full Member
  • ***
  • Posts: 118
Re: MathEx, a proposal
« Reply #5 on: October 04, 2017, 11:19:13 pm »
I've read something about big integer operations using a library in this link:
http://forum.lazarus.freepascal.org/index.php/topic,33764.msg219222.html#msg219222
And it's impressive.
I did some tests whith Diffie-Helmann key exchange and it was very fast.
Take a look and see if it helps.

CuriousKit

  • Jr. Member
  • **
  • Posts: 78
Re: MathEx, a proposal
« Reply #6 on: October 04, 2017, 11:26:12 pm »
That's a nice idea Phil - thanks.

Admittedly I didn't think about writing a 1000x1000 matrix multiply function, although what you describe sounds like calculating a determinant, whose speed upon a naïve implementation is O(n³), with the theoretical limit at O(n²)), while doing a dot product between two 1000-component vectors is a fairly trivial operation that I don't think you can do any faster than O(n), although the FMA operations will help a lot here.  Granted, manipulating such matrices can be useful in some linear programming problems.  It's something I'll keep on the list though!

A while ago I wrote a bunch of vector routines using everything from Pascal to raw 386 opcodes (with x87 floating-point operations), then SSE, AVX and FMA, selecting the best one that the hardware supports, while also doing a lot of benchmarking during development to ensure it actually IS faster than a previous instruction set!  Unfortunately, the only usable computer I have currently is an old laptop that only goes up to AVX... i.e. no FMA, AMX2 or BMI2.

Of course, the drawback to having versions for all the different instruction sets that is selected at run-time is a larger binary size and some overhead on initialisation, but a lot of it can be cut out of x86-64, for example, because 64-bit Windows will not install if the processor doesn't at least support SSE2.

Anyway, enough rambling!

So far I have a number of vector and matrix routines to port over that are designed for game engines, so hopefully those will be welcome, and routines for modular arithmetic that is mostly for my own thing, but might see some uses elsewhere, who knows!

To hrayon: what I'm currently building is less about big integer operations and more about parallel computation on lots of small integers simultaneously, so the two complement rather than compete with each other.  Still, I'll be taking a look!

Regarding big integers, I mostly use gmp.  Unfortunately, it's written in C (and assembler) so I have to communicate with it through a DLL.  Having this ported to Pascal would be wonderful though because I can see some speed increases due to less overhead.  Saying that, I haven't managed to get gmp to compile on 64-bit Windows yet, only 32-bit.
« Last Edit: October 04, 2017, 11:29:31 pm by CuriousKit »

Phil

  • Hero Member
  • *****
  • Posts: 2737
Re: MathEx, a proposal
« Reply #7 on: October 04, 2017, 11:48:14 pm »
Unfortunately, the only usable computer I have currently is an old laptop that only goes up to AVX... i.e. no FMA, AMX2 or BMI2.

The t2.micro instance on AWS (1 year free) gives you Intel Xeon E5-2676 v3 @ 2.40 GHz.


So far I have a number of vector and matrix routines to port over that are designed for game engines, so hopefully those will be welcome, and routines for modular arithmetic that is mostly for my own thing, but might see some uses elsewhere, who knows!

Have you looked at what's already available on users' computers? For example, all of Apple's platforms (desktop, mobile, etc.) include the Accelerate framework (versioned library):

https://developer.apple.com/documentation/accelerate

CuriousKit

  • Jr. Member
  • **
  • Posts: 78
Re: MathEx, a proposal
« Reply #8 on: October 05, 2017, 12:11:26 am »
I confess I've had very little exposure to Apple products in general (I'm averse to iPhones!), so I wasn't aware of Accelerate.  I know there are a number of C libraries out there for mathematics, but I'm not sure if there's really a standard one to go for, or one that's particularly compatible with Pascal.  Most of the matrix and vector libraries I've seen just have naïve implementations - yes they work, but could be so much better!  Still, if you can enlighten me, I stand humbled and corrected.
« Last Edit: October 05, 2017, 12:12:59 am by CuriousKit »

Phil

  • Hero Member
  • *****
  • Posts: 2737
Re: MathEx, a proposal
« Reply #9 on: October 05, 2017, 12:18:22 am »
I confess I've had very little exposure to Apple products in general (I'm averse to iPhones!), so I wasn't aware of Accelerate.  I know there are a number of C libraries out there for mathematics, but I'm not sure if there's really a standard one to go for, or one that's particularly compatible with Pascal.  Most of the matrix and vector libraries I've seen just have naïve implementations - yes they work, but could be so much better!  Still, if you can enlighten me, I stand humbled and corrected.

I'm afraid I don't know anything about the Accelerate framework or whether it's available on other platforms. Often Apple includes standard open source libraries such as SQLite and OpenCL on all of their platforms, but I don't know if that's the case with Accelerate or any parts of it. Note that Apple invented OpenCL, which also might be of interest to you:

https://en.wikipedia.org/wiki/Open_Compute_Library

https://developer.apple.com/library/content/documentation/Performance/Conceptual/OpenCL_MacProgGuide/Introduction/Introduction.html#//apple_ref/doc/uid/TP40008312

OpenCL should be available on Linux and Windows too. Somebody here was asking about it recently, I think, maybe search for that posting.



CuriousKit

  • Jr. Member
  • **
  • Posts: 78
Re: MathEx, a proposal
« Reply #10 on: October 05, 2017, 12:54:20 am »
Interesting. I did stumble across OpenCL before but couldn't really do much with it because I don't have a dedicated graphics card available (I only have funds for low-end laptops currently!), so normally, when doing a matrix multiplication in this case, it's faster to do hand-coded assembly or even a high level language because you don't have the overhead of configuring and calling OpenCL which only has the single CPU and its cores to play with.  Nevertheless, when I do get a more powerful rig, OpenCL certainly looks like something fun to play around with for number theory-related experiments.

I'll keep playing around with coding for the time being and eventually show what I've done.  My ambition is to make something general-purpose, useful and maybe standard to the Free Pascal community, but I best not get ahead of myself or be too much of a know-it-all showoff.

----

My personal project, which involves factoring Fermat numbers (numbers of the form 2^2^N + 1), does involve both parallel division against prime numbers and the use of gmp for large integers.  The latter tests full factors against a representation of the Fermat number (since sometimes even the full version is impractical to store in memory... e.g. for F32, the number requires 4,294,967,297 bits of storage, all but the first and last are zeroes), while the former takes part of the factor to be tested (trial division to help filter out impossible factors) and recombines the fragments at the end with modular multiplication, some of which can be pre-computed.
« Last Edit: October 05, 2017, 01:01:02 am by CuriousKit »

 

TinyPortal © 2005-2018