PHP User Warning: fetch_template() calls should be replaced by the vB_Template class. Template name: bbcode_highlight in ..../includes/functions.php on line 4197
[RESOLVED] BigInteger slow performance-VBForums
Results 1 to 22 of 22

Thread: [RESOLVED] BigInteger slow performance

  1. #1

    Thread Starter
    Addicted Member
    Join Date
    Oct 2018
    Posts
    136

    Resolved [RESOLVED] BigInteger slow performance

    I want to play with biginteger class, but I encountered performance issues - itīs slow for 600 000 digits (calculation). Itīs possible to speed up biginteger and compute results that contains 10 000 000 digits?

    How can I alter biginteger representation type?

  2. #2
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    34,914

    Re: BigInteger slow performance

    Define slow.

    BigInteger will naturally be slower than normal calculations, as calculations require considerably more work than a standard integer calculation. So, how fast do you need it to be? You probably won't be able to get there, though there may be an alternate solution that will work, such as doing a series of calculations in parallel. That depends on the problem, though.

    As for representation type, what would you like there? All numbers are displayed as strings, and there would be no difference for BigInteger. Text on the screen is a string, regardless of whether it is displaying a number or something else. Technically, a string might be an array of bytes, though, so it could be represented as an array of bytes. Using that logic, a BigInteger can be represented as an array of something, though whether that would be bytes, integers, long integers, or something more exotic I can't say.
    My usual boring signature: Nothing

  3. #3

    Thread Starter
    Addicted Member
    Join Date
    Oct 2018
    Posts
    136

    Re: BigInteger slow performance

    Quote Originally Posted by Shaggy Hiker View Post
    Define slow.
    Slow for calculation 123578^127812 - result contains 650812 digits an it tooks 40 seconds to generate result in textbox.

    Quote Originally Posted by Shaggy Hiker View Post
    As for representation type, what would you like there?
    I want to represent biginteger as text... or convert bytes to text interpretation directly. As one member said:

    The easiest implementation of a BigInteger would use a String to represent the number internally, or an array of digits. That means the "biggest" number you can represent is limited by how much memory you have.

  4. #4
    Frenzied Member
    Join Date
    Jul 2011
    Location
    UK
    Posts
    1,282

    Re: BigInteger slow performance

    Quote Originally Posted by VB.NET Developer View Post
    Slow for calculation 123578^127812 - result contains 650812 digits an it tooks 40 seconds to generate result in textbox.



    I want to represent biginteger as text... or convert bytes to text interpretation directly. As one member said:
    Of that 40 seconds, the calculation will be taking about 7 seconds.

    The other 33 seconds is how long it takes to convert the BigInteger result to a 650812 digit string.

    However, converting the BigInteger result to a 270244 element Byte array takes about 4 milliseconds.

    Yeah, working with BigIntegers is a lot slower than normal numeric types. The bigger they are , the slower they get. Avoid converting to and from Strings until you absolutely have to.

  5. #5
    Hyperactive Member
    Join Date
    Nov 2017
    Location
    Buckingham, UK
    Posts
    260

    Re: BigInteger slow performance

    Quote Originally Posted by VB.NET Developer View Post
    Slow for calculation 123578^127812 - result contains 650812 digits an it tooks 40 seconds to generate result in textbox. .... I want to represent biginteger as text... or convert bytes to text interpretation directly. As one member said:
    I'm probably missing something, since I struggle to think of any reason one would have for wanting to display all of a 650812-digit number (or what purpose that would serve).

    As has been said, it's probably activities associated with the 'displaying' (not the calculating) which are probably responsible for the lion's share of your run time.

    Kind Regards, John

  6. #6
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    34,914

    Re: BigInteger slow performance

    Quote Originally Posted by JohnW2 View Post
    I'm probably missing something, since I struggle to think of any reason one would have for wanting to display all of a 650812-digit number (or what purpose that would serve).

    As has been said, it's probably activities associated with the 'displaying' (not the calculating) which are probably responsible for the lion's share of your run time.

    Kind Regards, John
    I totally support this post.

    Nobody can look at a string that large and have it mean anything at all to them. That would be a string the size of a book, and not a small book at that. You probably couldn't display it anywhere, so it wouldn't be meaningful as a string.

    In a different thread, you mentioned storing to a file. For that, you would only need the bytes, which would be particularly quick, as Inferred pointed out. So, don't go through a string as an intermediary, since it would be so worthless for a string that size.

    Using a string to represent a huge number internally is viable, but it is slow, as well. I'm pretty sure that BigInteger uses an array of bytes internally, as math with that is relatively straightforward, if a bit slow. Using a string internally would be FAR less efficient, as there would be a whole lot of converting back and form to and from integers, and the string would end up taking up more space than the array of bytes would take up.
    My usual boring signature: Nothing

  7. #7
    Hyperactive Member
    Join Date
    Nov 2017
    Location
    Buckingham, UK
    Posts
    260

    Re: BigInteger slow performance

    Quote Originally Posted by Shaggy Hiker View Post
    I totally support this post. ... Nobody can look at a string that large and have it mean anything at all to them. That would be a string the size of a book, and not a small book at that. You probably couldn't display it anywhere, so it wouldn't be meaningful as a string.
    I'm glad that I'm not alone!

    Quote Originally Posted by Shaggy Hiker View Post
    Using a string to represent a huge number internally is viable, ...
    It is, but in the same vein as my previous comment, I can't think of a reason why one would want to store (let alone display) a number anything remotely as huge as we're talking about to the precision of a single digit. In some of the work I do, I deal with extremely large numbers, but very rarely need them to be displayed to even as much as a dozen significant figures and probably never 20 or more - so floating point storage (and limited precision display) invariably suffices for me.

    Since something is clearly going on here which is way beyond my experience, I would be fascinated if the OP could give us a little insight into the reason for needing what he appears to want!

    Kind Regards, John

  8. #8
    .NUT jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    104,719

    Re: BigInteger slow performance

    There's no way that they'd use a String representation internally because you can't do arithmetic on Strings. You have to convert back and forth between text and binary numbers to do anything useful so it would obviously be more efficient to store the data as a binary number and only convert in the minority of cases where a String is required. The source code for the type shows that that is the case.

    This thread is a demonstration of why it's important to test things for yourself first. As suggested, computation is not the issue but rather display. I just executed this code:
    vb.net Code:
    1. Imports System.Numerics
    2.  
    3. Module Module1
    4.  
    5.     Sub Main()
    6.         Dim n1 = 123456
    7.         Dim n2 = 567890
    8.  
    9.         Dim timer = Stopwatch.StartNew()
    10.  
    11.         Dim result = BigInteger.Pow(n2, n1)
    12.  
    13.         Console.WriteLine(timer.Elapsed)
    14.  
    15.         timer = Stopwatch.StartNew()
    16.  
    17.         Dim text = result.ToString()
    18.  
    19.         Console.WriteLine(timer.Elapsed)
    20.  
    21.         Console.ReadLine()
    22.     End Sub
    23.  
    24. End Module
    and this was the output:
    00:00:04.4874934
    00:00:25.5664163
    As you can see, the conversion from number to String takes over five times as long as the actual calculation. This code took a minute or two at the most to whip up so there's really no reason not to do it.
    Last edited by Shaggy Hiker; Nov 11th, 2019 at 10:00 PM. Reason: Fixed a typo.

  9. #9

    Thread Starter
    Addicted Member
    Join Date
    Oct 2018
    Posts
    136

    Re: BigInteger slow performance

    I tried this:
    Code:
    Using Writer As New System.IO.StreamWriter("C:\users\acer\desktop\biginteger_testBYTES.txt")
                Dim number1 = CType(TextBox1.Text, BigInteger)
                Dim number2 = CType(TextBox2.Text, BigInteger)
                Dim result As BigInteger = BigInteger.Pow(number1, CInt(number2))
                Dim byytes = result.ToByteArray
                Writer.Write(byytes)
            End Using
    but it only creates file with "System.Bytes()" text inside.

    I want to play with BigInteger capabilities - precisely, it has no upper limit, but I want to test the limit and view numbers... and see how far can I get! I expect results up to 1 000 000 000 000 000 000 digits in weeks. I previously thought that Long is good for testing, but itīs limited.

    Itīs not problem to wait days/weeks to finish, but if it can be faster, it will be good.
    Last edited by VB.NET Developer; Nov 13th, 2019 at 02:53 PM.

  10. #10
    Hyperactive Member
    Join Date
    Nov 2017
    Location
    Buckingham, UK
    Posts
    260

    Re: BigInteger slow performance

    Quote Originally Posted by VB.NET Developer View Post
    I want to play with BigInteger capabilities - precisely, it has no upper limit, but I want to test the limit and view numbers... and see how far can I get! I expect results up to 1 000 000 000 000 000 000 digits in weeks. I previously thought that Long is good for testing, but itīs limited.
    Is this purely an 'academic exercise'? As has been said, there would appear to be no practical/useful point in having numbers (whether integers or whatever) displayed to a ludicrous number of significant figures.

    Kind Regards, John

  11. #11
    Fanatic Member
    Join Date
    Nov 2017
    Posts
    1,006

    Re: BigInteger slow performance

    Quote Originally Posted by VB.NET Developer View Post
    I tried this:
    Code:
    Using Writer As New System.IO.StreamWriter("C:\users\acer\desktop\biginteger_testBYTES.txt")
                Dim number1 = CType(TextBox1.Text, BigInteger)
                Dim number2 = CType(TextBox2.Text, BigInteger)
                Dim result As BigInteger = BigInteger.Pow(number1, CInt(number2))
                Dim byytes = result.ToByteArray
                Writer.Write(byytes)
            End Using
    but it only creates file with "System.Bytes()" text inside.

    I want to play with BigInteger capabilities - precisely, it has no upper limit, but I want to test the limit and view numbers... and see how far can I get! I expect results up to 1 000 000 000 000 000 000 digits in weeks. I previously thought that Long is good for testing, but itīs limited.

    Itīs not problem to wait days/weeks to finish, but if it can be faster, it will be good.
    Really. Numbers up to 1 quintillion digits. Lets set aside the fact that RAM limitation will be encountered long before disk space is used up. Do you know how much disk space would be needed to store a 1 quintillion digit number at 1 byte per digit? Pretty easy conversion. 1 quintillion bytes. Or 1 Exabyte. Spoiler alert before you look up how much that is - its too much for you to work with.

    Good luck.

  12. #12
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    34,914

    Re: BigInteger slow performance

    StreamWriter.Write has a variety of overloads which take a variety of different arguments, but not one of those takes an array of bytes as an argument. It DOES take an array of Char, but not an array of bytes. So, with Option Strict ON, that write line should have resulted in an error. Since it did not, and since you got the type as output, I assume that the compiler noticed that no overload of Write takes an array of bytes, but that .ToString was implemented (as it is on all objects), so it called .ToString on the type and used the overload of Write that takes a string.

    So, if you switch from a StreamWriter to a BinaryWriter, which DOES have a Write that takes an array of Bytes, then that should work...sort of. You end up with a binary file, which may not be what you want...or maybe it is. I can't say, because it all seems so hopeless. As OB1 noted, you'll never be able to write out the numbers you are talking about because there isn't enough storage for a single number of that size. You might be able to get up around a billion digits, or maybe even a few billion, but you're talking about a million GB, and nobody has that.

    The other hopeless element is putting such a number into a file. If you DID put it into a text file, it wouldn't be useful, since you can't read a number that big. The file would be enormous, and dull as can be. Therefore, if you just want the file for storage, a binary file using a binary writer is good enough.
    My usual boring signature: Nothing

  13. #13

    Thread Starter
    Addicted Member
    Join Date
    Oct 2018
    Posts
    136

    Re: BigInteger slow performance

    Is this purely an 'academic exercise'?
    Yes, it is. Three days ago, one student at school where I am working as system admin asks me if theīs something to work with very large numbers thatīs fast. I told him that online solutions exists, but it doesnīt meet him criteria. So I tell him that I can try to make one software to deal with huge numbers. Of course, I warned him that computation will take toooooo long and displaying that size will be useless. So he tells me that it wil be enough for him if I could make software thatīs able to handle approx. 100 000 000 digits. Anything longer than that, it will be useless.

    Iīll try to look at binarywriter when Iīll at home.

  14. #14
    Hyperactive Member
    Join Date
    Nov 2017
    Location
    Buckingham, UK
    Posts
    260

    Re: BigInteger slow performance

    Quote Originally Posted by VB.NET Developer View Post
    Yes, it is. Three days ago, one student at school where I am working as system admin asks me if theīs something to work with very large numbers thatīs fast. ..... So he tells me that it wil be enough for him if I could make software thatīs able to handle approx. 100 000 000 digits.
    That really only moves my question one person down the line! Do you know if it is just an 'academic exercise' for the student, or whether he has some actual reason to need to be able to deal with such extraordinary numbers?

    Kind Regards, John

  15. #15
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    34,914

    Re: BigInteger slow performance

    I agree with that. Whenever we get a question about super large, pretty nearly unusable, numbers, the story behind them is usually one of futility. Somebody has an idea of something that would work if the numbers were smaller, but once they get large enough, whatever the goal is involves a number of iterations that exceed the lifespan of the average human, if not the lifespan of the sun itself. I have yet to see such a request where the ultimate goal was achievable.
    My usual boring signature: Nothing

  16. #16
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    5,914

    Re: BigInteger slow performance

    There are a fair number of people who work with really large numbers, in various competitions, which a member of another programming board used to be quite active in. Unfortunately, that forum is no more.
    But an example would be that earlier this year, a new record has been set, calculating Pi to 31.4 trillion digits. Of course, it wasn't done on a single computer, but relied on using Google cloud technology to achieve the required storage and calculation needs.
    "Anyone can do any amount of work, provided it isn't the work he is supposed to be doing at that moment" Robert Benchley, 1930

  17. #17
    Hyperactive Member
    Join Date
    Nov 2017
    Location
    Buckingham, UK
    Posts
    260

    Re: BigInteger slow performance

    Quote Originally Posted by Shaggy Hiker View Post
    I agree with that. Whenever we get a question about super large, pretty nearly unusable, numbers, the story behind them is usually one of futility.
    Indeed so. Under most circumstances, its not the magnitude of the number which is the issue but, rather, the question of precision. As I've said, I sometimes work with extremely large numbers, but never need a precision (or display) greater than a modest handful of significant digits - so standard floating-point numbers (and calculation) are fine, and require a trivial amount of storage space.

    The only situation of which I'm aware in which there might be an issue is when propagated errors may arise during extremely large numbers of calculations - in which case it may be necessary to undertake the calculation with pretty high-precision, even though one doesn't require the end-result to be anything like that precise - but, even then, I feel sure that there are no real-world situations in which one would need to calculate with a 'ludicrous' degree of precision!

    Exercises such as the calculation of pi to a 'near-infinite' number of decimal places (as mentioned by passel) are, again, really only academic exercises - and are really 'done simply because they can be done'!

    Kind Regards, John

  18. #18
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    34,914

    Re: BigInteger slow performance

    Quote Originally Posted by passel View Post
    There are a fair number of people who work with really large numbers, in various competitions, which a member of another programming board used to be quite active in. Unfortunately, that forum is no more.
    But an example would be that earlier this year, a new record has been set, calculating Pi to 31.4 trillion digits. Of course, it wasn't done on a single computer, but relied on using Google cloud technology to achieve the required storage and calculation needs.
    Well....that's a really pie in the sky calculation, right?
    My usual boring signature: Nothing

  19. #19
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    5,914

    Re: BigInteger slow performance

    Quote Originally Posted by Shaggy Hiker View Post
    Well....that's a really pie in the sky calculation, right?
    Write. A merged double pun, I like it.
    "Anyone can do any amount of work, provided it isn't the work he is supposed to be doing at that moment" Robert Benchley, 1930

  20. #20

    Thread Starter
    Addicted Member
    Join Date
    Oct 2018
    Posts
    136

    Re: BigInteger slow performance

    Thanks Shaggy Hiker! Now it works as expected, though I must told student tomorrow that calculations of numbers of that size is pointless until he is scientist.

  21. #21
    Hyperactive Member
    Join Date
    Nov 2017
    Location
    Buckingham, UK
    Posts
    260

    Re: BigInteger slow performance

    Quote Originally Posted by VB.NET Developer View Post
    Thanks Shaggy Hiker! Now it works as expected, though I must told student tomorrow that calculations of numbers of that size is pointless until he is scientist.
    Maybe "... pointless even if/when he becomes a scientist"?

    Kind Regards, John

  22. #22

    Thread Starter
    Addicted Member
    Join Date
    Oct 2018
    Posts
    136

    Re: BigInteger slow performance

    Quote Originally Posted by JohnW2 View Post
    Maybe "... pointless even if/when he becomes a scientist"?
    Yes. Thanks for correction!

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Featured


Click Here to Expand Forum to Full Width