1

Background

I work in the field of financial trading and am currently optimizing a real-time C# trading application.

Through extensive profiling I have identified that the performance of System.Decimal is now a bottleneck. As a result I am currently coding up a couple of more efficient fixed scale 64-bit 'decimal' structures (one signed, one unsigned) to perform base10 arithmatic. Using a fixed scale of 9 (i.e. 9 digits after the decimal point) means the underlying 64-bit integer can be used to represent the values:

-9,223,372,036.854775808 to 9,223,372,036.854775807

and

0 to 18,446,744,073.709551615

respectively.

This makes most operations trivial (i.e. comparisons, addition, subtraction). However, for multiplication and division I am currently falling back on the implementation provided by System.Decimal. I assume the external FCallMultiply method it invokes for multiplication uses either the Karatsuba or Toom–Cook algorithm under the covers. For division, I'm not sure which particular algorithm it would use.

Question

Does anyone know if, due to the fixed scale of my decimal values, there are any faster multiplication and division algorithms I can employ which are likely to out-perform System.Decimal.

I would appreciate your thoughts...

0b101010
  • 756
  • 6
  • 15
  • 2
    Make sure you VERY carefully unit test this against expected results. We wouldn't want a custom math library to trigger the next financial collapse. – Eric J. Apr 30 '15 at 17:59
  • If you are using integers to represent fixed point values, why can you not just use integer multiplication and division? – Tim Long Apr 30 '15 at 18:21
  • @Eric J. Don't worry the unit tests check every operation across EVERY possible value against the same operation performed on System.Decimal. Needless to say the full suite takes hours to run. – 0b101010 Apr 30 '15 at 22:00
  • @Tim Long In a word, overflows. The majority of arguments would result in an integer overflow. – 0b101010 Apr 30 '15 at 22:02

2 Answers2

3

I have done something similar, by using the Schönhage Strassen algorithm.

I cannot find any sources now, but you can try to convert this code to the C# language.

P.S. i cannot say for sure about System.Decimal, but the "Karatsuba algorithm" is used by System.Numerics.BigInteger

Alexandre Ostapenko
  • 164
  • 7
  • Thanks. Dont want to reinvent the wheel so will investigate the performance of using BigInt's implementations. – 0b101010 May 01 '15 at 09:01
  • May i have a + for my rep? :) – Alexandre Ostapenko May 01 '15 at 09:33
  • 1
    A +rep for suggesting Schönhage-Strassen for ~double width integer computation? Single width fixed point? – greybeard May 01 '15 at 10:39
  • Interesting, I have just tested a multiplication implementation using `BigInteger` and it's 250% slower than the `Decimal` call to `FCallMultiply`. I also tried out an open source optimized 128bit integer type (https://github.com/ricksladkey/dirichlet-numerics) and that tested at 30% slower. It looks very much like the native method invoked by `FCallMultiply` gives the best performance. – 0b101010 May 20 '15 at 17:20
0

My take of fixed point arithmetic (in general, not knowing about about C# or .NET in particular (VS Express acting up) (then, there's Fixed point math in c#? and Why no fixed point type in C#?):

  • The main point is a fixed scale - and that this is conceptual, first and foremost - the hardware couldn't care less about meaning/interpretation of numbers (or much anything) (unless it supports something, if for marketing reasons)
  • the easy: addition/subtraction - just ignore scaling
  • multiplication: compute the double-wide product, divide by scale
  • division: multiply (widened) dividend by scale and divide
  • the ugly - transcendental functions beyond exponentiation (exponentiate, multiply by scale to half that power)
  • in choosing a scale, don't forget conversion to and from digits, which may vastly outnumber multiplication&division (and give using a square a thought, see above …)

That said, "multiples of word size" and powers of two have been popular choices for scale due to speed in multiplying and dividing by such a scale. This still may make a difference with contemporary processors, if not for main ALUs of PCs - think SIMD extensions, GPUs, embedded …
Given what little I was able to discern of your application and requirements (consider disclosing more), three generic choices to consider are 10^9 (to the 9th power), 2^30 and 2^32. The latter representations may be called 34.30 and 32.32 for the bit lengths of their integral and fractional parts, respectively.

With a language that allows to create types (especially supporting operators in addition to invokable procedures), I deem designing and implementing that new type according the principle of least surprise important.

Community
  • 1
  • 1
greybeard
  • 2,249
  • 8
  • 30
  • 66
  • Thanks for taking the time to write up an answer. I don't understand though how I would be able to perform accurate base10 arithmetic operations if I was to use the base2 representations suggested (e.g. 34.30 and 32.32). I read the links you referenced before posting my question but they both seem to only deal with base2 arithmetic. – 0b101010 May 05 '15 at 12:22
  • Just try the first choice mentioned. Not elaborating rsn on pretext of being busy, but reading Annex A of ISO/IEC Tech Rep 18037 may be well worth it. For the pinched: [... C - Extensions ...](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf) – greybeard May 06 '15 at 12:44
  • Thanks for the link. Had a bit of spare time and read the Annex as suggested and picked up some useful info. Nothing there though which specifically helps with my question unfortunately. If I were implementing a base2 fixed point type then things would be very different. But this type must support accurate base10 operations. The multiplication and division operations (whilst trivial in principle) cannot be easily achieved without implementing some sort of non-trivial algorithm to handle integers > 64bits (due to the risk of overflows). – 0b101010 May 20 '15 at 14:26
  • One must assume that is why Microsoft's .NET BCL team chose to implement multiplication of their `BigInteger` type using Karatsuba. Although, having looked at the `BigInteger` source code I'm not sure a more efficient solution can't be found. – 0b101010 May 20 '15 at 14:27