Go Back > Math Stuff > Computer Science & Computational Number Theory

Thread Tools
Old 2020-05-29, 19:46   #1
Jan 2018

2 Posts
Default Addition Chains for Mersenne Numbers

I am have been obsessed with the Mersenne numbers for quite a few years but for a different reason than most people here.
We define \(l(n)\) as the length of the smallest addition chain for \(n\).

I am desperately trying to find an addition chain for \(2^n-1\) thats short:

\(l(2^n-1) < n + l(n) - 1\)

I have covered all cases with \(l(n)\leq9\) so that has \(n\leq512\) to give you some idea of the sizes of the integers. The first case I can't handle is \(n=127\).

I expect I can learn a lot from what you guys do. My first source of performance problems is caused by me using boost for large integers on Windows. boost layers on top of compiler support for 128 bit integers that are unsupported in windows for both the MSVC c++ compiler and the Intel c++ compiler. So it ends up doing calculations in 32 bit chunks rather than 64 bit. I used fixed size integers in boost rather than the dynamic versions.
What do you guys use or suggest for these size integers? The most complex thing I do is division and I try to limit that as it kills my performance.
NeillC is offline   Reply With Quote
Old 2020-05-29, 20:22   #2
VBCurtis's Avatar
Feb 2005
Riverside, CA

11×383 Posts
Default : arbitrary precision.
VBCurtis is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
New Mersenne Software For Test Mersenne Prime Numbers On Android thorken Software 66 2019-01-13 21:08
On prime chains Dougy Math 10 2009-09-11 21:05
Best practices in addition chains SPWorley Programming 10 2009-07-28 13:50
6 digit numbers and the mersenne numbers henryzz Math 2 2008-04-29 02:05
LLT numbers, linkd with Mersenne and Fermat numbers T.Rex Math 4 2005-05-07 08:25

All times are UTC. The time now is 14:06.

Fri Jul 10 14:06:48 UTC 2020 up 107 days, 11:39, 1 user, load averages: 2.27, 2.29, 2.09

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.