Question and Requests

May 1, 2009 at 12:52 AM
I've just looked through the docs and interfaces and have a couple requests and a question. First of all, there seems to be something pretty obvious missing: converting an IntX to a standard data type like long, ulong, int, uint, etc. Sure these won't hold all 128 bits, but they should truncate.

Next, I'd like to see support for Guids, or at least a byte[] array, which a Guid can be easily turned into.

Finally, support for higher bases than 16 would be nice. Personally I'd like to see this go all the way up to 62, with the option to customize whether uppercase or lowercase is considered higher (I suggest 0-9, A-Z, a-z as default).

The latter two are just "would be nice" things, but the first question is actually a problem for me. I'm hoping I can just use the internal "digits" array to truncate the number manually. Is this correct? Would I use index 0 of the array like myIntX._digits[0]?
May 1, 2009 at 12:56 AM
If you allowed a custom character array to be specified, you could support arbitrary base conversions by taking digits based on the index in the array. I could then construct my own character array containing the digits 0-9, A-Z, a-z and pass this to the base conversion method. Conversely, you could do the opposite direction by looking-up each character of a string in the array to find its index using Array.IndexOf<char>(), though that would probably be rather inefficient.
Coordinator
Jan 21, 2010 at 6:19 PM

Thanks for your post, unfortunately I saw it now only. I have added explicit conversion to int/uint/long/ulong/ushort into recent build 0.9.3.1 which you can download from site.

I am not going to add support for Guid conversion because it's a non-primitive and not often used type. There can be many similar types and I just can't add support for every one of them :) since this will be incorrect from the library design point of view. If you need to convert Guid into IntX and vice versa I suggest you to use IntX constructor which obtains array of digits and method GetInternalState() which returns this array. Array stores IntX digits as 4-byte uint values, digit with index 0 is a lowest one. If you have byte array then you can convert it into uint[] array and vice versa using standard System.BitConverter class from BCL.

Jan 21, 2010 at 9:14 PM
Edited Jan 21, 2010 at 9:26 PM

Hello first let me say thanks for putting this lib together.  This functionality is conspicuous by its absence in the .NET framework.  I'm also pleased you implemnted the explicit conversion, that was something I desired (but worked around).  I'm not sure if I have found a bug or if I am merely misusing the lib, but leading 0's seem to anger the IntX parser.  For example:

IntX.Parse("123") naturally works fine, but IntX.Parse("0123") yields an exception "Digit is too big for this base.".  Please advise.  Thank you!

p.s. I attempted to pull the source to check it out myself but it isn't available through SVN.  Am I just being dumb? :)

Coordinator
Jan 22, 2010 at 9:34 AM
Edited Jan 22, 2010 at 12:18 PM

For me IntX.Parse("0123") works fine. However, IntX.Parse("08") won't work and this is by intention since IntX.Parse() without base provided explicitly treats integers starting from "0" as integers in 8-base and integers starting from "0x" as in 16-base (hexadecimal). If you know that you are always supplying 10-base integer then use overload which allows to provide base explicitly. I am not going to change this since this can break a lot of existing code which uses IntX. However, I will add description of this feature into method XML documentation.

Oh, and there is no SVN since there is no ability to contribute into the project - I don't have a time to really coordinate something. However, all the source code is available in the archive, "src" folder.

Coordinator
Jan 22, 2010 at 5:19 PM

chaiguy1337, I have added support for parsing/converting to string IntX with base > 16 and custom alphabet as it was requested by you. You can find new functionality in fresh release 0.9.3.2.

Jan 26, 2010 at 12:28 AM

I was wondering if it would be possible to update the library to use an optimized method for squaring an IntX. I understand that you are using FHT for multiplication, but I imagine their is a way that FHT can be optimized for squaring.

I attempted to apply the karatasuba sqaure algorithm, but the results are about 4 times slower than the FHT.

I made the _digits public and have tried the following:

 

Function KaratsubaSq(ByVal x As IntX) As IntX
        If x._digits.Length < 1024 Then
            Return x * x
        Else
            x.Normalize()
            Dim Length As Integer = x._digits.Length

            If Length Mod 2 <> 0 Then 
                Length += 1 '4
            End If
            Dim Mid As Integer = Length \ 2 
            Dim Left(Mid - 1) As UInteger
            Array.Copy(x._digits, Left, Mid) 
            Dim Right(Mid - 1) As UInteger
            Array.Copy(x._digits, Mid, Right, 0, x._digits.Length - Mid) 

            Dim L As IntX = New IntX(Left, False)
            Dim R As IntX = New IntX(Right, False)

            Dim M As IntX = (L * R) << ((Mid * 32) + 1)
            R = Me.KaratsubaSq(R)
            L = Me.KaratsubaSq(L)
            R <<= (Length * 32)
            Dim Result As IntX = L + R + M

            Result.Normalize()
            Return Result
        End If


    End Function

 

Coordinator
Jan 26, 2010 at 9:36 AM

Karatsuba algorithm is asymptotically slower that FHT-based algorithm so it won't be faster that FHT-based approach. And there is no way to speed up FHT-based multiplication using Karatsuba algorithm - they just can't work together. Read more theory to understand. If you need the highest multiplication speed possible I'd suggest you trying out GMP library - see more details on IntX project home page.