This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.
Messages - ruler501
16
« on: February 05, 2014, 01:40:01 pm »
I do have the same denominator a lot(order of 2*3^12 to 2 * 3^13 times in the current run), but I can't cache all of them because that would be 2*3^15 different values(stored in 8 bytes each) which would be 219mb of data(actually this might be reasonable) I might try to find a way to just pass it in so it doesn't have to be stored.
I'll do that later today and speed test it to see if there is any significant benefit.
17
« on: February 04, 2014, 03:32:29 pm »
That's the only problem I found. I'll post my whole program later
Edit: also my code will never give it more than 3^20 and unsigned long long shouldn't overflow till 3^40
EDIT2: Here's the whole program. It is counting all rationals with denominators(in simplest form) between 3^n and 3^(n+1) in the cantor set
#include <iostream>
#include <algorithm>
#include <thread>
#include <cmath>
#define THREADS 8
using namespace std;
bool testCantor(unsigned long long p, unsigned long long q){
while(q % 3 == 0){
q /= 3;
if(p/q == 1) return p == q;
p %= q;
}
unsigned long long p_start = p;
do{
unsigned long long p3 = p * 3;
if(p3/q == 1) return false;
p = p3 % q;
} while(p != p_start);
return true;
}
void genRational(unsigned long long minNum, unsigned long long maxNum, int jump, unsigned long long *result){
for(unsigned long long q = minNum; q <= maxNum; q += jump)
for(unsigned long long p = 1; p < q/3; p++)
if(p % 3 != 0 && testCantor(p, q) && __gcd(p,q) == 1)
for(unsigned long long i = p; i < q/3; i *= 3)
(*result) += 2 * (__gcd(i,q) == 1);
}
int main(int argc, char* argv[]){
int n = argc;
unsigned long long minNum = pow(3, n), *tempLongLong = nullptr, maxNum = pow(3, n+1), result = 0;
vector<thread*> usedThreads;
vector<unsigned long long*> results;
thread* tempThread = nullptr;
for(int i = 0; i < THREADS; i++){
tempLongLong = new unsigned long long(0);
results.push_back(tempLongLong);
tempThread = new thread(genRational, minNum + i, maxNum, THREADS, tempLongLong);
usedThreads.push_back(tempThread);
}
for(auto i = usedThreads.begin(); i != usedThreads.end(); i++) (*i)->join();
for(auto i = results.begin(); i != results.end(); i++) result += **i;
cout << n << " " << result << endl;
}
EDIT: Used an additional property for halving the search space(if a number x is in the cantor set then 1-x is also in the set). I haven't tested the code yet(using windows which stubbornly won't compile if I'm using threads)
EDIT2: Have it down to only checking 2/9 of the rationals(though depending on rounding may miss 1, but that should barely affect results)
also as a note to calcdude84se your else statements in the function didn't actually do anything(the if returned so execution stopped there if it was true), so I removed them. Not sure if that actually boosts performance though.
18
« on: February 04, 2014, 02:35:58 pm »
It runs slightly faster than mine did and is much more accurate. One problem though your check for p/q==1 needs to return p==q not false because if it terminates with a 1 it is in the Cantor set (change the 1 to a 0 and add repeating 2 after it)
19
« on: February 03, 2014, 05:05:58 pm »
Is there a fast way to test for membership in the cantor set. My only idea is to test out to some threshold(25 digits or so) and if there are no ones(in ternary) before that to assume it is in the cantor set. This might work, but it is likely to include more rationals than it should(though q will always be under 3^20). Is there a better(preferably fast) way to do this? My code currently spends 97% of it's time in this function(though it is called ~2 million times) and any improvements will give me massive performance boosts.
This is my current code(THRESH is 70 which should be more precision than unsigned long long provides)
bool testCantor(unsigned long long p, unsigned long long q)
{
unsigned long double rem = ((long double)p)/q, div = ((long double)1)/3;
int test;
unsigned long long mult = 3;
for(int i=0; i<THRESH; i++)
{
test = rem * mult;
if(test == 1)
{
if(rem > div) return false;
else return true;
}
rem -= test*div;
mult *= 3;
div /= 3;
}
return true;
}
20
« on: January 30, 2014, 11:32:50 am »
if it's an i5 or a xeon hyperthreading shouldn't really matter
21
« on: January 30, 2014, 10:56:51 am »
Actually looking online it seems that they are pretty much the same(though you can't overclock the xeons it seems).
22
« on: January 30, 2014, 02:41:41 am »
There are more benefits to the i5/i7 line than just the GPU. I'd think you could get an i5 for the same price.
The GPU looks good though.
23
« on: January 30, 2014, 02:33:38 am »
I would be happy if we had another competition. I could put up an amazon gift card($25) for it.
I'd like a computer competition, but anything that helps the community is good.
24
« on: December 31, 2013, 10:12:57 pm »
No room on my desk for it  Monitors and microwave(with printer on top). Take up all the space. Edited first post to include all the upgrades added and other updated infromation
25
« on: December 31, 2013, 05:47:10 pm »
BUMP
I was gone for a week but just got back and ordered the SSD and cooler. They should be here later this week. I still have ~400 I could spend if there are worthwhile upgrades for that price(if I get a second graphics card for crossfire I'll probably need a new PSU)
26
« on: December 25, 2013, 08:24:25 pm »
I got some money for computer upgrades, a memory foam pad for my dorm room bad, a t-shirt, klipsch image s4i(which actually work pretty well with my s4 just volume buttons don't work) earbuds, a nice new wallet, and a suitcase for when I go to England this summer.
28
« on: December 12, 2013, 03:14:27 pm »
It is a great coin. has random block reward and is valued at a wide range, but I usually get about $11 per 10k
29
« on: December 12, 2013, 12:30:23 pm »
Doge coin is a good alt coin to try with. There is no exchange that carries it but you can trade it on there forum. I have made $58 and 0.02BTC in ~36 hours
30
« on: December 10, 2013, 11:44:27 pm »
It approaches 1 as the length goes to infinity. For any value \delta more than 0 you can choose a natural number N so that the number .99999... with N digits or more will be within \delta of 1.
|
Show Posts