mersenneforum.org (https://www.mersenneforum.org/index.php)
-   y-cruncher (https://www.mersenneforum.org/forumdisplay.php?f=159)
-   -   31.4 ... 62.8 ... 100 trillion digits of Pi - GWR (https://www.mersenneforum.org/showthread.php?t=25155)

 De Wandelaar 2020-02-06 21:23

The problem of long and short scales :[URL="https://en.wikipedia.org/wiki/Long_and_short_scales"]https://en.wikipedia.org/wiki/Long_and_short_scales[/URL] … but 5E13 is already in itself a terrific result !

[QUOTE=paulunderwood;536878]5E19? I think it is 5E13. :whack:

[/QUOTE]

 R. Gerbicz 2020-02-07 09:19

[QUOTE=Uncwilly;536903]655 words per minute. And since digits are short words, it is doable.

[url]https://www.guinnessworldrecords.com/world-records/358936-fastest-talker[/url][/QUOTE]

"Sean Shannon (Canada) recited Hamlet's soliloquy `To be or not to be' (260 words) in a time of 23.8 seconds"

Doable, pretty short words.

 LaurV 2020-02-07 09:42

Do they have a record for the "longest" speaker? Like the person who talked without a pause for a while?

(we wanted to send the former link to swmbo with the title "someone have beaten you already" but it occured to us that she's actually not a fast speaker, so we refrained ourselves on doing such a terrible mistake... :razz:)

 Mysticial 2020-02-07 09:47

Woah, I go away for a while and didn't notice all these new posts!

[QUOTE=LaurV;536456]Very nice, congrats!

How do you make the base switch "in place"? I have some ideas how to transform from base 2 to base 10 quite fast and also have some checkpoints, but you would need more storage space (it can't really be done "in place"), and I don't believe this is new, for sure somebody else was thinking to it before. I "invented" it long time ago and used it in my programs in the past, but never for such large inputs.[/QUOTE]

It's not fully in-place in that it doesn't need any auxiliary memory. It needs a lot actually - especially to perform the FFTs.

But there are a few technicalities:

The large multiplications are done in-place. So the output overwrites the inputs. (the multiplication is still done using the FFT scratch buffers)

1) One problem is that I don't support checkpointing inside the large multiplications. Thus I can only checkpoint before or after a large multiplication. But if you encapsulate the multiplication into an indivisible operation, it becomes a destructive operation that destroys the inputs. Thus if something goes wrong inside the multiply, you cannot roll back to before the multiply because you've already destroyed the inputs.

This in-place-ness of the multiplications within the base-conversion will chain up. Thus there's no point where you can do a checkpoint other than before the entire conversion begins.

2) The other problem is that checkpointing is done with file-granularity. I don't support checkpointing parts of a file. The binary->radix conversions involve recursively splitting up the binary input into smaller and smaller portions which you eventually write piecewise into a large output buffer (in the desired radix).

The presents a problem. That output buffer is allocated as single contiguous storage region as a single file. I can't write to parts of the file, checkpoint it, then write to other parts. The reason I can't do that is due sector alignment.

Let's say the following is a partially written sector that's been checkpointed:

0123456789xxxxxx

Then in a later operation, I want to write out the rest of the sector so that it is:

0123456789abcdef

However. When you access disk, the entire sector must be read/written at once. The later operation needs to do a read-modify-write to data that is part of the previous checkpoint. If something goes wrong during this step, it will corrupt the previous checkpoint!

----------------

Long story short, I believe both of issues are surmountable. But I haven't done the necessary research into it yet.

For example, the in-place-ness issue (1) can be overcome by having two working buffers and writing back-and-forth between them. But the base conversion already uses the most storage of the entire computation.

The sector-alignment is probably solvable by keeping a separate mapping that stores backups of all partially written sectors. But saying that this is a mess in the context of the software raid layer and manual error-detection checksums is an understatement.

 Mysticial 2020-02-07 10:14

[QUOTE=LaurV;536456]Very nice, congrats!

How do you make the base switch "in place"? I have some ideas how to transform from base 2 to base 10 quite fast and also have some checkpoints, but you would need more storage space (it can't really be done "in place"), and I don't believe this is new, for sure somebody else was thinking to it before. I "invented" it long time ago and used it in my programs in the past, but never for such large inputs.[/QUOTE]

To answer your actual question of how I do the conversion "in place". The algorithm is the scaled remainder tree. The only operations are multiplications. There are no additions or subtractions at all.

Each multiply is a middle-product FFT that splits a 2N-bit binary input into two N-bit binary outputs which are written back into the same memory - overwriting the 2N-bit input. One of the N-bit outputs is the same as the upper-half of the 2B-bit output. Thus instead of overwriting the entire memory region, the "new" N-bit output overwrites the no-longer-needed portion of the 2N-bit input. This partial write is hard to checkpoint due to problem (2) of the previous post.

Since the in-place multiply is the only operation for the entire radix conversion, these in-place multiplications form a dependency chain/tree that prevents any sort of checkpointing at any step.

 Dr Sardonicus 2020-02-09 02:45

[QUOTE=LaurV;536949]Do they have a record for the "longest" speaker? Like the person who talked without a pause for a while?
<snip>[/QUOTE]The most recent record for "longest speech marathon" I could find at [url=https://www.guinnessworldrecords.com/world-records/longest-speech-marathon/]Guinness[/url] is just over 90 hours:

[quote]The longest speech marathon is 90 hr and 2 min, achieved by Ananta Ram KC (Nepal) in Kathmandu, Nepal from 27 to 31 August 2018.

The attempt started at 6:15 am on 27th August and finished at 12:17 am on 31st August 2018. Ananta Ram KC maintained a silence for almost 7 days before starting the attempt as a part of his preparation for the longest speech attempt.[/quote]

In a story about an [url=https://www.guinnessworldrecords.com/news/charity/2014/6/new-longest-speech-marathon-record-raises-£25k-for-sue-ryder-hospice-appeal-357830?fb_comment_id=1105337029484095_1158992957451835]earlier record[/url] (2014) in this category, I found:[quote]Under Guinness World Records guidelines, a speech is defined as, "the act of delivering a formal spoken communication to an audience," meaning using footage, clips or audio is strictly prohibited.

Notes are allowed, written copy, autocues and prompters are not; making Rob's 46 hour 21 minute-long achievement all the more impressive.[/quote]

 MooMoo2 2020-05-19 04:32

[QUOTE=mackerel;536373]Reading this I almost want to have a go. Almost... That storage requirement is scary...[/QUOTE]
You can certainly have a go at the other records. The program used to calculate pi to 50 trillion digits has also been used to calculate square roots, logarithms, and various constants to billions of decimal places. I held the record for ln (2) at one point:

[url]https://www.mersenneforum.org/showpost.php?p=502462&postcount=716[/url]
[url]http://www.numberworld.org/digits/Log(2)/[/url]

 bbb120 2020-11-17 06:18

[QUOTE=Mysticial;536256]So when Google set the record of 31.4 trillion digits last year, I gave it a 50/50 chance that record would fall before the end of the year.

Didn't quite work out that way. This latest computation suffered about a month of setbacks that pushed it all the way through January. But it is finally complete and passes verification.

Congrats to Timothy Mullican for setting the new record for the most digits of Pi!

His Blog: [url]https://blog.timothymullican.com/calculating-pi-my-attempt-breaking-pi-record[/url]

Compared to the Google's record last year, Tim used a 4-socket Ivy Bridge machine with a 48-drive array. The computation ran for 10 months starting from April and ending yesterday.

The computation of the binary digits of Pi actually completed early in December and matched the results of BBP spot check. But the base conversion (which takes 2 weeks and has no checkpoints) took several attempts before completing successfully.

--------------------

This base conversion has been an issue in 3 or the last 4 Pi records due to it being ~10% of the total time and having no checkpoints at all. 10% run-time of these computations of this size equates to multiple weeks - which is also comparable to the MTTF of the systems that are used.

Why don't I have checkpoints in the base conversion? The algorithm is largely in-place and destructive. That's not to say it's impossible to checkpoint, but I just haven't figured out a good way to do it yet.[/QUOTE]

What are the advantages of y-cruncher ?
Why can it calculate so many digits?
[url]https://www.mersenneforum.org/showpost.php?p=562790&postcount=14[/url]
why we can calculate 50 trillion digits of Pi ,but cannot test a PRP test on F33，
F33 only has no more than 2700 billion digits

 Stargate38 2020-11-17 18:02

Because the time complexity for pi calculation is much better/faster than that of primality/PRP tests. Also F33 has 2,585,827,973 digits, not 2.7 trillion (which is more like F43).

 storm5510 2020-11-17 18:29

[QUOTE=bbb120;563454]What are the advantages of y-cruncher ?
Why can it calculate so many digits?
[URL]https://www.mersenneforum.org/showpost.php?p=562790&postcount=14[/URL]
why we can calculate 50 trillion digits of Pi ,but cannot test a PRP test on F33，
F33 only has no more than 2700 billion digits[/QUOTE]

I messed with Y-Cruncher a little. It appears to serve no practical purpose in the context of GIMPS.

Some years ago, I saw a photo of a system built by a man in Japan on a sheet of plywood. He had an array of hard drives totaling 105 TB, I believe it was. 21 drives. The odd drive was OS only. The rest was for storage and swap, like a huge paging file. I don't remember it saying how much RAM he had on it or the CPU type. He had it all arranged very nicely. The drives were in stacked brackets with extra fans on them. The PSU was very large. It looked like a small computer tower sitting off to one side. IIRC, it took him nearly a year to run 11.4 trillion digits, which was a new record at the time. Y-Cruncher seems to prefer vast amounts of swap/storage space on drives over lot of RAM. The Japanese man must have spent a small fortune buying all the parts to build what he had.

 bbb120 2020-11-18 01:05

[QUOTE=Stargate38;563531]Because the time complexity for pi calculation is much better/faster than that of primality/PRP tests. Also F33 has 2,585,827,973 digits, not 2.7 trillion (which is more like F43).[/QUOTE]

F33 only has no more than 2700 billion digits
it should be "F33 only has no more than 2700 million digits"
I make a mistake !
floor(2^33*log(2)+1)=floor(2585827973.98)

2,585,827,973=2_585_827_973 (English)
2,585,827,973=25_8582_7973(chinese)
I am not familiar with three digits separated number ,all Chinese four digits separated number , so I make a mistake

All times are UTC. The time now is 18:16.