mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2012-07-12, 12:03   #1
NullCoding
 
Jul 2012
Carlisle, PA USA

410 Posts
Default Using Programming to earn Primes

I'm completely self-taught in programming. I've used this username since 2008 or so, but needless to say, it used to be accurate!

Lately I've been teaching myself C++, which means I have also been learning C. I tend to approach things first from a C perspective, and then see how C++ re-implements that function if applicable.

I'm not looking for programming tips so much as very specific advice I feel like I would definitely find on this forum (and not many other places).

I've only been at it for a week or so, but I have written a small program that accurately calculates Proth numbers based on a user input of k and a value of 2^n from a pre-made input file (a simple array). I used a simple for loop to find factors. You can see the code here.

That program is obviously very limited. But it's useful if you want to check if 11 or 47 are indeed still prime.

Now I'm working on a version using the MPIR library, which I assume is known here as a fork of GMP. I'd love to eventually use gwnum as well, since I've seen through PrimeGrid what it's capable of. I tried installing FFTW as well, but those libraries use decorated functions and I've a 64-bit system, so there are some incompatibilities I've yet to sort out.

Using MPIR, I have gotten the program to accept user input of k and input from a file in a manner identical to my previous program - except this file contains up to 2^100 - and subsequently return a possibly very large Proth number. I am still working on a feasible division loop, since there is no distinct modulus function I can evaluate in MPIR (it returns an integer as a separate function).

I am NOT trying to make a program that'll rival LLR! I'm trying to make one that does the same thing with numbers many orders of magnitude smaller simply for the sake of learning programming. I'd rather start with something familiar (number theory) - no matter how complicated the program gets, I'll understand the output, meaning I'll know I messed up if, say, 95 is consistently evaluated as prime.

I guess I wanted to ask here before I get way too deep in doing things potentially wrong.

Would it make more sense to simply create an array of smaller known primes and sequentially test the candidate against those?

I am not sure how exactly to do that but I'm sure I could figure it out.

I'd be happy to share my code, but it doesn't really work at the moment. It loops incorrectly and tells you that some numbers ending in a 5 are prime. Perhaps if there's interest I will post it anyway.

I just thought I'd come here for advice writing some kind of simplistic primality testing program (again, for education's sake) - any advice would be great!
NullCoding is offline   Reply With Quote
Old 2012-07-12, 15:26   #2
bearnol
 
bearnol's Avatar
 
Sep 2005

127 Posts
Default

Interesting... let us know how it goes...
So I looked up Proth's theorem on Wikipedia, somehow not having come across it before, and regrettably there wasn't a proof there, but:
Incidentally, I wonder if PT could be extended thusly (or similar! :) :
let p = k2^n + 1 as before, but w/ k<2^(n+i)
and a^(p-1)/(2^(1+i)) == -1 [mod p]
(with random a having 1/(2^(i+1)) chance of positive witness)
and if so, whether this would be useful?
J
bearnol is offline   Reply With Quote
Old 2012-07-13, 20:05   #3
NullCoding
 
Jul 2012
Carlisle, PA USA

22 Posts
Default

That could be useful, yes. I have yet to implement checks such as 2^n must be greater than k, k cannot (well, shouldn't) be even, etc. For the most part, the MPIR library is good about returning 0 at exceptions as opposed to outright crashing.

I actually finished the program and called it a beta because it works. Got a little carried away and made a full "release" package of it in case someone for some reason wishes to build it in VS2010 from source.

This is my project - only gjs15x64_release.rar is relevant, as the other versions don't use MPIR at all...

By the way (off topic) are you by chance the one in charge of WEP-M+2 project? I run that project on most of my *nix boxes. I think I might be ranked #1 in average credit. Funny running into you here!
NullCoding is offline   Reply With Quote
Old 2012-07-13, 20:43   #4
bearnol
 
bearnol's Avatar
 
Sep 2005

127 Posts
Default

Yep, that's me - thanks for your contribution to WEP-M+2. (I had also wondered if that might be you :) In fact I guess, if I'm honest, that had partly inspired my post here!
J
bearnol is offline   Reply With Quote
Old 2012-07-14, 20:07   #5
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default Assuming I read the title right...

It hurts me too
D
davieddy is offline   Reply With Quote
Old 2012-07-14, 22:28   #6
NBtarheel_33
 
NBtarheel_33's Avatar
 
"Nathan"
Jul 2008
Maryland, USA

5·223 Posts
Default

Re: the title - Would this be at all related to the Prime Number Sh!tting Bear?
NBtarheel_33 is offline   Reply With Quote
Old 2012-07-14, 23:22   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2·13·443 Posts
Default

Quote:
Originally Posted by NBtarheel_33 View Post
Re: the title - Would this be at all related to the Prime Number Sh!tting Bear?
Can't comment on the possible connection with Ursus Primus Puppis, but I can make the following funny anagram out of it:

"Using Primes to learn Programming"
ewmayer is offline   Reply With Quote
Old 2012-07-15, 01:58   #8
NullCoding
 
Jul 2012
Carlisle, PA USA

416 Posts
Default

Is this someone's idea of a joke?

I was being serious. I guess this forum isn't the right place for my ideas after all.
NullCoding is offline   Reply With Quote
Old 2012-07-15, 02:01   #9
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

Quote:
Originally Posted by NullCoding View Post
Is this someone's idea of a joke?

I was being serious. I guess this forum isn't the right place for my ideas after all.
Anything in the "Extra Stuff" group is vulnerable to title changes. Typically the conversion moves apace after a few posts commenting on the title change. See, e.g., http://www.mersenneforum.org/showthread.php?t=16728 (and notice of course that the new title is an anagram of the old one). (Another hint: I certainly didn't choose "Basketry That Evening" as my title, but hey.)

I personally haven't posted previously because I can be of absolutely no use to you. (Even if my knowledge of programming was as advanced as yours, the math is still beyond me.)

Last fiddled with by Dubslow on 2012-07-15 at 02:03
Dubslow is offline   Reply With Quote
Old 2012-07-15, 02:08   #10
NullCoding
 
Jul 2012
Carlisle, PA USA

48 Posts
Default

So...you people just change titles for the hell of it?

As someone new to these particular fora, but not fora in general, that's more than a bit odd. I'm a moderator of a forum with millions of users...if I changed titles to be funny, I'd be banned. But then again, I never was any good at anagrams.

And my program most certainly does not urinate primes. Every now and then it finds one lying around somewhere by chance, that's all. You just have to tell it where to look.

I appreciate the compliment but I have only been learning programming for about a week and a half. Hardly advanced.

I guess I'll include the URL anyway in case someone's interested. Also there's a GUI now.
NullCoding is offline   Reply With Quote
Old 2012-07-15, 02:17   #11
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

194A16 Posts
Default

Quote:
Originally Posted by NullCoding View Post
Is this someone's idea of a joke?

I was being serious. I guess this forum isn't the right place for my ideas after all.
Takes a few posts to get used to it.
Welcome aboard!

D

Our ship is sinking...
but we don't give a damn

Last fiddled with by davieddy on 2012-07-15 at 02:28
davieddy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Programming a Conjecture devarajkandadai Miscellaneous Math 16 2016-12-03 17:00
Need some help on php programming pinhodecarlos Programming 2 2012-07-23 18:17
New to programming. What to do? lorgix Miscellaneous Math 9 2010-12-08 22:22
plz, help me in c programming alaa Homework Help 12 2007-06-12 22:17
Programming a Test devarajkandadai Miscellaneous Math 17 2005-03-30 05:18

All times are UTC. The time now is 12:12.

Mon Sep 28 12:12:47 UTC 2020 up 18 days, 9:23, 0 users, load averages: 2.28, 2.43, 2.07

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.