* * *

Author Topic: BigNumbers: yet another library for calculating with very big natural numbers  (Read 13202 times)

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 5538
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #15 on: September 18, 2013, 07:43:34 pm »
Ah well, allowing for up yo 2G digits has it's price.

That's because you store one digit per byte, while it has room for log10(256)=2.4 digits.

Storing binary might require to decimal to binary and vice versa operations though. I don't know how complicated they are (if they are single or multiple pass)

Still, even by storing 2 digits per byte (packed BCD) the efficiency rises from  1/2.4 to 2/2.4 (from 41% to 83%)

Bart

  • Hero Member
  • *****
  • Posts: 2675
    • Bart en Mariska's Webstek
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #16 on: September 18, 2013, 11:14:41 pm »
That's because you store one digit per byte, while it has room for log10(256)=2.4 digits.

Storing binary might require to decimal to binary and vice versa operations though. I don't know how complicated they are (if they are single or multiple pass)

Obviously you have more knowledge than I regarding this.
I'm not sure how I would be able to do that.
It would require a complete re-thinking of the basic algorithms (add, sub, mul; all the others are basically derived) and storage.
The ono-on-one representation in the storage made it kind of "simple" to derive the required algorithms (and to understand them reading back the code).

Anyhow, thanks for the feedback.

Bart

Bart

  • Hero Member
  • *****
  • Posts: 2675
    • Bart en Mariska's Webstek
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #17 on: September 18, 2013, 11:28:55 pm »
Mmmm... you're tempting me to locate some list of Latin inscriptions and find one that does have such ridiculous values... AFAIR, not everybody went by the same rules when taking hammer and chisel - not surprising given that inscriptions vary between 100s of years BC and say 1900... or even later...
Well, that obviously is a problem.
There are many more "Roman" systems out there, using more than the MDLCXVI letters.
Also in the middle ages o.a. they put horizontal lines above and under the letters, indicating that the number should be multiplied by 1000 (see http://en.wikipedia.org/wiki/Roman_numerals).
But since we cannot enter that as text, I see no way to parse it.

Generally there are some rules though.
  • A smaller number in front of a larger number means subtraction, all else means addition. For example, IV means 4, VI means 6.
  • You would not put more than one smaller number in front of a larger number to subtract. For example, IIV would not mean 3.
  • You must separate ones, tens, hundreds, and thousands as separate items. That means that 99 is XCIX, 90 + 9, but never should be written as IC. Similarly, 999 cannot be IM and 1999 cannot be MIM.
  • From M you can only subtract C, from D only C, from C only X, from L only X, from X only I, from V only I
  • Groups (like MCM, CCC, IV, I) can only be ordered from high to low. So once you are in the hundreds, there can never be a following 500 or 1000.

And while that is rather easy to see, it prooved rather more difficult to implement.
Bart

BigChimp

  • Hero Member
  • *****
  • Posts: 5740
  • Add to the wiki - it's free ;)
    • FPCUp, PaperTiger scanning and other open source projects
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #18 on: September 19, 2013, 08:38:05 am »
(see http://en.wikipedia.org/wiki/Roman_numerals).
Yes.
Generally there are some rules though.
And, IIRC, the article above says the existing rules (as far as there were indeed rules, as the entire article indicates there were a lot of changes) were broken sometimes as well. Don't know if those broken rules would be rejected by your code though (e.g. using IIII instead of IV, or having DCCCC instead of CM for 90 (edit: arrrgh should be 900 of course) may well be accepted)...

Never mind though, only pedants would be mad enough to try this. Does this say anything about me ;)
« Last Edit: September 20, 2013, 08:58:39 am by BigChimp »
Want quicker answers to your questions? Read http://wiki.lazarus.freepascal.org/Lazarus_Faq#What_is_the_correct_way_to_ask_questions_in_the_forum.3F

Open source including papertiger OCR/PDF scanning:
https://bitbucket.org/reiniero

Lazarus trunk+FPC trunk x86, Windows x64 unless otherwise specified

Mike.Cornflake

  • Hero Member
  • *****
  • Posts: 1125
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #19 on: September 19, 2013, 09:15:55 am »
Quote
Never mind though, only pedants would be mad enough to try this. Does this say anything about me ;)

Well, I can now picture you walking around graveyards, looking at headstones and groaning "THAT wont compile!?!"  :D
Lazarus Trunk/FPC Trunk on Linux & Windows [7, 8.1]
  Have you tried searching this forum or the wiki?:   http://wiki.lazarus.freepascal.org/Alternative_Main_Page
  BOOKS! (Free and otherwise): http://wiki.lazarus.freepascal.org/Pascal_and_Lazarus_Books_and_Magazines

Bart

  • Hero Member
  • *****
  • Posts: 2675
    • Bart en Mariska's Webstek
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #20 on: September 19, 2013, 06:10:42 pm »
Don't know if those broken rules would be rejected by your code though (e.g. using IIII instead of IV, or having DCCCC instead of CM for 90 may well be accepted)...

Well, I have decided to accept DCCCC as 900, and IIII as 4, since this is more frequently seen.
Most important rule (and AFAIK followed by most "implementations") is the order of groups, and the subtraction rule (only one).
So M cannot follow after e.g. L, and X cannot follow I (except IX, and this then must end the string).

Never mind though, only pedants would be mad enough to try this. Does this say anything about me ;)

To try what: implementing some RomanToNumber function (the author of StrUtils.RomanToInt would be very glad to hear this), or my library as a total.
Depending on the answer to that question, the answer to the your question may be either yes or no (not necessarily in that order though) ;D

Bart

BigChimp

  • Hero Member
  • *****
  • Posts: 5740
  • Add to the wiki - it's free ;)
    • FPCUp, PaperTiger scanning and other open source projects
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #21 on: September 20, 2013, 09:02:55 am »
Most important rule (and AFAIK followed by most "implementations") is the order of groups, and the subtraction rule (only one).
So M cannot follow after e.g. L, and X cannot follow I (except IX, and this then must end the string).
I agree.

Never mind though, only pedants would be mad enough to try this. Does this say anything about me ;)

To try what: implementing some RomanToNumber function (the author of StrUtils.RomanToInt would be very glad to hear this), or my library as a total.
Depending on the answer to that question, the answer to the your question may be either yes or no (not necessarily in that order though) ;D
Well actually, I meant trying to input ridiculous values into either function (rather than implementing any code). Regardless, I hope you can agree that in all cases the answer may actually not be yes or no, but XLII ;)
Want quicker answers to your questions? Read http://wiki.lazarus.freepascal.org/Lazarus_Faq#What_is_the_correct_way_to_ask_questions_in_the_forum.3F

Open source including papertiger OCR/PDF scanning:
https://bitbucket.org/reiniero

Lazarus trunk+FPC trunk x86, Windows x64 unless otherwise specified

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 5538
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #22 on: September 20, 2013, 03:20:01 pm »
Never mind though, only pedants would be mad enough to try this. Does this say anything about me ;)

To try what: implementing some RomanToNumber function (the author of StrUtils.RomanToInt would be very glad to hear this), or my library as a total.

I think he meant that the Romans left very few digital resources. (probably because digital media were only invented some 1400 years after the fall of the empire)

Btw, the algorithms wouldn't be that different. It is just that instead of anything "10 or above" provoking a carry, it is now anything 2^32 and above :-)
 

Bart

  • Hero Member
  • *****
  • Posts: 2675
    • Bart en Mariska's Webstek
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #23 on: September 20, 2013, 04:56:21 pm »
Regardless, I hope you can agree that in all cases the answer may actually not be yes or no, but XLII ;)

Of course, since that is the ultimate answer to the ultimate question.

Bart

Bart

  • Hero Member
  • *****
  • Posts: 2675
    • Bart en Mariska's Webstek
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #24 on: September 20, 2013, 04:57:21 pm »
I think he meant that the Romans left very few digital resources. (probably because digital media were only invented some 1400 years after the fall of the empire)

That's a lame excuse, they (the Romans) just didn't try...
Even in (o.a.) the Menoic civilization (appr 400 AC) they already used tablets.

Bart
« Last Edit: September 20, 2013, 06:16:21 pm by Bart »

Bart

  • Hero Member
  • *****
  • Posts: 2675
    • Bart en Mariska's Webstek
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #25 on: September 20, 2013, 08:19:07 pm »
Implemented conversions to and from Octal.

Bart

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 5538
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #26 on: September 20, 2013, 08:54:48 pm »

Even in (o.a.) the Menoic civilization (appr 400 AC) they already used tablets.

(The Roman Republic starts +/- 500 BC, and before that there was the Kingdom, wikipedia seems to
put founding to around 750BC. Longer if you count Alba Longa (the royal family of which Romulus and Remus
were said to be linked to, and it was the capital of Latium before Rome))


Yeah, but they were not digital screens. I assume they were analog CRT's or so, or something as else with the same relevance as Roman numerals nowadays :-)

Bart

  • Hero Member
  • *****
  • Posts: 2675
    • Bart en Mariska's Webstek
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #27 on: September 21, 2013, 09:55:47 pm »

Even in (o.a.) the Menoic civilization (appr 400 AC) they already used tablets.
That should have read BC. Sorry for the confusion.

Yeah, but they were not digital screens. I assume they were analog CRT's or so,
Well, they resemble the iPad, kinda...

Bart

Bart

  • Hero Member
  • *****
  • Posts: 2675
    • Bart en Mariska's Webstek
Implemented Lucas and Fibonacci series.

Bart

djzepi

  • New member
  • *
  • Posts: 32
Hi

Could you add also Leonardo number


The Leonardo Sequence is the series of numbers:

 1, 1, 3, 5, 9, 15, 25 ...

http://wiki.lazarus.freepascal.org/Leonardo_number

 

Recent

Get Lazarus at SourceForge.net. Fast, secure and Free Open Source software downloads Open Hub project report for Lazarus