Author Topic: An astronomical number  (Read 5936 times)

raymond

  • Member
  • ***
  • Posts: 318
    • Raymond's page
An astronomical number
« on: January 17, 2022, 01:32:13 PM »
I was toying with some math principals the other day. It's amazing how what seems to be some 'simple' input can turn out such extreme numbers.

The first part had to do with the digit sum of numbers (in the decimal system). For example, the digit sum of 31495 would be 3+1+4+9+5=22. However, there is an infinite variety of numbers having that same digit sum. The main idea was to find the smallest number having a given digit sum. In this case, the smallest one would be 499 (4+9+9=22).

The next part had to do with the Fibonacci sequence. For those not familiar with it, it starts with 0 and 1 as the first two numbers in the sequence. The next number is obtained by adding the previous two numbers, giving:
0,1,1,2,3,5,8,13,21,34,55,...
55 being the tenth one and denoted as F10.

Although F90 is not a small number by any means, it still fits within the 64-bit binary format. But, the smallest number which would have a digit sum equal to F90 would be so big that if you wanted to print it on a strip of paper with letter-size width, 100 characters per line, 100 lines per foot, that strip of paper would reach well beyond the orbit of Pluto. AND, if you had a super fast printer which could produce at a rate of 100 feet/second, it would take some 4.5 million years to finish the job!!! :dazzled:
Whenever you assume something, you risk being wrong half the time.
http://www.ray.masmcode.com/

daydreamer

  • Member
  • *****
  • Posts: 2307
  • my kind of REAL10 Blonde
Re: An astronomical number
« Reply #1 on: January 17, 2022, 08:17:01 PM »
The first part had to do with the digit sum of numbers (in the decimal system). For example, the digit sum of 31495 would be 3+1+4+9+5=22. However, there is an infinite variety of numbers having that same digit sum. The main idea was to find the smallest number having a given digit sum. In this case, the smallest one would be 499 (4+9+9=22).

The next part had to do with the Fibonacci sequence. For those not familiar with it, it starts with 0 and 1 as the first two numbers in the sequence. The next number is obtained by adding the previous two numbers, giving:
0,1,1,2,3,5,8,13,21,34,55,...
55 being the tenth one and denoted as F10.

are you sure,isnt all numbers that add up to 22 some factorial 1!,2!,3!,4!,5!,6!,7!,8!,9! ?
used for 21 black jack game probability ?

fibonacci
discovered they appear alot in nature,for example sunflower seeds is placed in one fibonnaci "rows" and following fibonnaci "columns",its actually curved
they had second biggest prime number finder on tv documentary about maths,he found it by have his computer crunch numbers for 5 years
but fibonnaci done with ascii,endless adc until out of memory
 
my none asm creations
http://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

daydreamer

  • Member
  • *****
  • Posts: 2307
  • my kind of REAL10 Blonde
Re: An astronomical number
« Reply #2 on: January 18, 2022, 09:43:48 PM »
I was just curious so I tested with 128bit DECIMAL type and
Code: [Select]
139th fibonnaci 5009530124805839113932791626129 digits




« Last Edit: January 19, 2022, 04:02:19 AM by daydreamer »
my none asm creations
http://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

raymond

  • Member
  • ***
  • Posts: 318
    • Raymond's page
Re: An astronomical number
« Reply #3 on: January 20, 2022, 05:50:56 AM »
I confirm your value for F139, with my mega-million decimal type.

For your info (and others' as well), here's my value for the first Fibonacci number to reach 100 digits, i.e. F476:
1344719667586153181419716641724567886890850696275767987106294472017884974410332069524504824747437757

And, F4782 would be the first one to reach 1000 digits.
« Last Edit: January 20, 2022, 02:56:48 PM by raymond »
Whenever you assume something, you risk being wrong half the time.
http://www.ray.masmcode.com/

daydreamer

  • Member
  • *****
  • Posts: 2307
  • my kind of REAL10 Blonde
Re: An astronomical number
« Reply #4 on: January 20, 2022, 11:01:25 PM »
thanks raymond :thumbsup:
wonder how fast lots of digits fibonnaci can be made to go?

 



« Last Edit: January 21, 2022, 03:19:45 AM by daydreamer »
my none asm creations
http://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

daydreamer

  • Member
  • *****
  • Posts: 2307
  • my kind of REAL10 Blonde
Re: An astronomical number
« Reply #5 on: January 22, 2022, 10:31:16 PM »
I made an attempt with fibonnaci ,allocate few million bytes memory,but a bug made it crash
was aiming for find the first over 1000000 fibonnaci number
so I instead went for get it right with
.data
f1 db 1024 dup("0")
cr db 0

my none asm creations
http://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

raymond

  • Member
  • ***
  • Posts: 318
    • Raymond's page
Re: An astronomical number
« Reply #6 on: January 23, 2022, 03:59:42 AM »
Just for curiosity, F47847 would be the first one to have 10000 digits. That took an entire 0.5 second on my old laptop.

Based on previous results, my estimate would be close to F478495 to get the first one with 100000 digits, and may take between 30 seconds and a minute. But, going for the million digits may increase the time to well over an hour and could be just before arriving at F4785000.

I'm tempted.


Amazing! It is actually F478495 being the first to reach 100000 digits, and it took 53 seconds. Now for the million!!!!
Whenever you assume something, you risk being wrong half the time.
http://www.ray.masmcode.com/

daydreamer

  • Member
  • *****
  • Posts: 2307
  • my kind of REAL10 Blonde
Re: An astronomical number
« Reply #7 on: January 23, 2022, 10:46:04 AM »
I am going for 1million,Unrolled loops
F2100000



« Last Edit: January 24, 2022, 12:45:37 AM by daydreamer »
my none asm creations
http://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

raymond

  • Member
  • ***
  • Posts: 318
    • Raymond's page
Re: An astronomical number
« Reply #8 on: January 24, 2022, 10:35:22 AM »
It only took a shade less than an hour and a half, about 100 times longer than for the 100,000th. F4784969 is the first one to reach the million digits.

The leading 7 digits are 1072739 and the least significant 8 digits would be 78405156.

I don't think Hutch would appreciate a posting of the whole number in this thread! :nie: :undecided:
Whenever you assume something, you risk being wrong half the time.
http://www.ray.masmcode.com/

daydreamer

  • Member
  • *****
  • Posts: 2307
  • my kind of REAL10 Blonde
Re: An astronomical number
« Reply #9 on: January 24, 2022, 11:29:19 PM »
Great raymond  :thumbsup:
Biggest over 500000 to be able To zip here?
Biggest possible in 32bit 1billion in size?
I wanna know how to get bigger many million stack?
Quote
fibonnaci nr 2002
with two print two fibonnaci in loop
Quote
fibonnaci millis  1297
with print buffer that holds two fibonnaci nr in loop
Quote
fibonnaci millis  735
without print,only final print
Quote
fibonnaci millis  16
« Last Edit: January 26, 2022, 01:47:33 AM by daydreamer »
my none asm creations
http://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

jack

  • Member
  • **
  • Posts: 223
Re: An astronomical number
« Reply #10 on: January 26, 2022, 10:38:49 AM »
@raymond
I wrote my own arbitrary precision floating point routines and calculated fibonacci(4784969) by using the formula ( ( (1+sqrt(5))/2 )^n - ( (1-sqrt(5))/2 )^n )/sqrt(5)
it took 25 minutes 18 seconds but the last 10 digits are 8405156269 I verified my result with Maple

raymond

  • Member
  • ***
  • Posts: 318
    • Raymond's page
Re: An astronomical number
« Reply #11 on: January 26, 2022, 02:12:05 PM »
Hi Jack,

Congratulations for your patience. Those Fibonacci numbers get to be pretty large pretty fast. BTW, I did mine with binary coded decimals which is 100% accurate.

Two points.

(i) Floating point computations with the given formula will only give you the eventual size of the Fibonacci number with some idea of the first few digits of that number, but certainly not any idea of the last few digits. Your accuracy would depend heavily on the accuracy of the sqrt(5) value which would need to be accurate to the 5,000,000th digit as a minimum to be used for computing F4784969 with the required accuracy.
Remember that a computation is only accurate to the accuracy level of the least accurate of its components

(ii) Whenever you mention the value of an F number, you should always add as reference which F value you would consider equal to 3; i.e. is it F2 (as starting with 1,2,3), F3 (as with 1,1,2,3), or F4) as with 0,1,1,2,3).
Whenever you assume something, you risk being wrong half the time.
http://www.ray.masmcode.com/

jack

  • Member
  • **
  • Posts: 223
Re: An astronomical number
« Reply #12 on: January 26, 2022, 11:47:38 PM »
hello raymond
I am an enthusiast of FreeBasic, I do most of my recreational programming it
I found a Fibonacci program on my HD created by Eric Olson, he implements basic BigNum routines to calculate the Fibonacci numbers using identities
     F(2k) = F(k)[2F(k+1)-F(k)]
   F(2k+1) = F(k+1)^2+F(k)^2
   F(2k+2) = F(k+1)[2F(k)+F(k+1)]
he later presents an optimized version that he uses in the program
     F(2k) = F(k)[2F(k+1)-F(k)]
   F(2k+1) = F(k+1)[2F(k+1)-F(k)]+(-1)^(k+1)
   F(2k+1) = F(k)[2F(k)+F(k+1)]+(-1)^(k)
   F(2k+2) = F(k+1)[2F(k)+F(k+1)]
on my PC to calculate Fibonacci(47849721) -- which gives a 10 million digits number, takes less than 6 minutes
you can find he's program in the BASIC folder at https://github.com/ZiCog/fibo_4784969 Eric's program is named fibo.bas
note that you need to change the constant nmax in line 28 to the desired precision/8 + a little extra
first 10 digits 8490335471 and the last 10 digits 8041866146
here's a zip file with the number https://u.pcloud.link/publink/show?code=XZU69rXZb6UTE84AQUQKcoikuxpQxjVjy407

an interesting read https://www.whitman.edu/documents/Academics/Mathematics/2015/Final%20Project%20-%20Shatkin.pdf

daydreamer

  • Member
  • *****
  • Posts: 2307
  • my kind of REAL10 Blonde
Re: An astronomical number
« Reply #13 on: January 27, 2022, 01:18:38 AM »
Great jack  :thumbsup:
Thanks raymond, made me realise I might need check reciprocal constants used to speed up div replace by mul, if I lose precision with replace it with 1/constant
Interesting read about overflow exception handler,wish I could write my own that handle decimal128 overflow with add second decimal variable same way adc= add with carry


my none asm creations
http://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

daydreamer

  • Member
  • *****
  • Posts: 2307
  • my kind of REAL10 Blonde
Re: An astronomical number
« Reply #14 on: January 31, 2022, 12:05:26 AM »
I can confirm that formula needs very accurate sqrt(5),because I tested calculate it with the usual fp types
or maybe I have a bug?
How far can you go with help of raymonds 9999 digits sqrt program ?

What works best with formula ? Round up or down?

« Last Edit: January 31, 2022, 01:34:52 AM by daydreamer »
my none asm creations
http://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding