Cooperative Agreement or Capitalist Takeover? You decide! - Page 6

davieddy · 2012-05-31, 00:00

Quote:

Originally Posted by Dubslow

But bear in mind that squaring a large number is very hard.

Or how about this: I'll give you £25 if you can write a program that can square a 12M digit number in 200 minutes on one core of a Core2. I don't think I could. Prime95 can do it in 90 ms.

Jeez (as Garo would say) I can't find my knees.

I'll waive the £25

Love as ever,
David

PS "Don't teach your Grandma how to suck eggs"

davieddy · 2012-05-31, 01:08

Quote:

Originally Posted by Dubslow

And do you think D or I could write even a basic FFT?

Assuming D is my good self I would reply in the affirmative.
As for you, keep on taking the tablets.
D

Dubslow · 2012-05-31, 01:23

Quote:

Originally Posted by davieddy

Assuming D is my good self I would reply in the affirmative.
As for you, keep on taking the tablets.
D

Well then excuse me for thinking such

Prime95 · 2012-05-31, 02:10

Mr. Bobrecki has responded. He has no objections to sharing factoring data. At first we'll probably use our respective web pages that query our databases. If you have any recommendations for him to make that easier, let us know.

I'm tempted to make BloodIce our official mers@home DB query manager :)

I've also pointed him to Oliver's CUDA code, so he may contact TheJudger at some point.

cheesehead · 2012-05-31, 05:25

Will some mod please change this thread's title to "Brainstorming ways to cooperate with Mersenne@home"?

I think that would be more suitable than my original title, since it's apparent by now that Mr. Bobrecki is open to a cooperating agreement and has no intention of competing.

flashjh · 2012-05-31, 05:54

Quote:

Originally Posted by cheesehead

Will some mod please change this thread's title to "Brainstorming ways to cooperate with Mersenne@home"?

I think that would be more suitable than my original title, since it's apparent by now that Mr. Bobrecki is open to a cooperating agreement and has no intention of competing.

'Cooperative Agreement or Communist Takeover? You decide!'

Nice touch

Dubslow · 2012-05-31, 07:24

Quote:

Originally Posted by flashjh

'Cooperative Agreement or Communist Takeover? You decide!'

Nice touch

Been changed again

LaurV · 2012-05-31, 08:09

Quote:

Originally Posted by Dubslow

But bear in mind that squaring a large number is very hard.

Or how about this: I'll give you £25 if you can write a program that can square a 12M digit number in 200 minutes on one core of a Core2. I don't think I could. Prime95 can do it in 90 ms.

Agree with you, but I won't waste the 25 bucks which you could lose very easy. I can produce a kinda karatsuba (don't need fft, just "divide and impera", mul(2^k*a+b, 2^k*c+d)=2^(2k)*mul(a,c)+2^k*(mul(a,d)+mul(b,c))+mul(b,d) in less then a hour in C, which would do the job in less then 200 minutes, for sure. I would bet on "under 10 minutes". Well, rework a bit the expression in the middle, this sounds like a school-grade complexity as it is written.

For the record, pari does it in 3 seconds (core2 duo, single core used, 2.8GHz, FFT, not optimized at all for this size).

Code:

(15:05:06) gp > #
   timer = 1 (on)
(15:05:25) gp > a=1<<45000000+random(1<<45000000);
  ***   at top-level: a=1<<45000000+random(1<
  ***                    ^--------------------
  *** _<<_: the PARI stack overflows !
  current stack size: 4000000 (3.815 Mbytes)
  [hint] you can increase GP stack with allocatemem()

  ***   Break loop: type 'break' to go back to GP
break>
(15:06:36) gp > allocatemem()
  ***   Warning: new stack size = 8000000 (7.629 Mbytes).
(15:06:43) gp > allocatemem()
  ***   Warning: new stack size = 16000000 (15.259 Mbytes).
(15:06:44) gp > allocatemem()
  ***   Warning: new stack size = 32000000 (30.518 Mbytes).
(15:06:45) gp > allocatemem()
  ***   Warning: new stack size = 64000000 (61.035 Mbytes).
(15:06:46) gp > allocatemem()
  ***   Warning: new stack size = 128000000 (122.070 Mbytes).
(15:06:46) gp > a=1<<45000000+random(1<<45000000);
time = 63 ms.
(15:06:51) gp > b=a^2;
time = 2,735 ms.
(15:07:07) gp >

edit: if you try the example, don't forget the semicolons at the end, which inhibit the printing. Otherwise you have to wait ages for the number to be printed, and eventually your pari can crash.

Dubslow · 2012-05-31, 08:30

Quote:

Originally Posted by LaurV

Agree with you, but I won't waste the 25 bucks which you could lose very easy. I can produce a kinda karatsuba (don't need fft, just "divide and impera", mul(2^k*a+b, 2^k*c+d)=2^(2k)*mul(a,c)+2^k*(mul(a,d)+mul(b,c))+mul(b,d) in less then a hour in C, which would do the job in less then 200 minutes, for sure. I would bet on "under 10 minutes". Well, rework a bit the expression in the middle, this sounds like a school-grade complexity as it is written.

For the record, pari does it in 3 seconds (core2 duo, single core used, 2.8GHz, FFT, not optimized at all for this size).

Code:

(15:05:06) gp > #
   timer = 1 (on)
(15:05:25) gp > a=1<<45000000+random(1<<45000000);
  ***   at top-level: a=1<<45000000+random(1<
  ***                    ^--------------------
  *** _<<_: the PARI stack overflows !
  current stack size: 4000000 (3.815 Mbytes)
  [hint] you can increase GP stack with allocatemem()

  ***   Break loop: type 'break' to go back to GP
break>
(15:06:36) gp > allocatemem()
  ***   Warning: new stack size = 8000000 (7.629 Mbytes).
(15:06:43) gp > allocatemem()
  ***   Warning: new stack size = 16000000 (15.259 Mbytes).
(15:06:44) gp > allocatemem()
  ***   Warning: new stack size = 32000000 (30.518 Mbytes).
(15:06:45) gp > allocatemem()
  ***   Warning: new stack size = 64000000 (61.035 Mbytes).
(15:06:46) gp > allocatemem()
  ***   Warning: new stack size = 128000000 (122.070 Mbytes).
(15:06:46) gp > a=1<<45000000+random(1<<45000000);
time = 63 ms.
(15:06:51) gp > b=a^2;
time = 2,735 ms.
(15:07:07) gp >

edit: if you try the example, don't forget the semicolons at the end, which inhibit the printing. Otherwise you have to wait ages for the number to be printed, and eventually your pari can crash.

edit2: lowering the limits after some goggle-ing. A copy-paste from this into my Excel (VBA) took 10 minutes to "adjust" and a minute to run on that big number. You would lose the money! hehe :P

Hey, I said write a program, meaning not pari or Excel or whatnot

I certainly would not have thought to write a general integer as a2^k+b and then square that instead.

LaurV · 2012-05-31, 08:38

yeah, whatever, I eliminated the second edit in my former post, as it was false

, I was posting before the calculus finished. It took about 15 minutes! grrrr... you can delete it from your post too, as the reference to VBA could be misleading too, for some who cant directly convert from pseudocode/pascal to vb). I would however keep the link, as the document is quite interesting for some beginner who wants to start experimenting with this.

edit, in fact it makes no sense to include the whole text when you reply to the last post...(and it is not really polite

, and not very cautious too, guys like me use to edit their last post many times, from English reasons, stupidity, tendency to boast, etc. hehe)

axn · 2012-05-31, 08:45

Quote:

Originally Posted by Dubslow

Hey, I said write a program, meaning not pari or Excel or whatnot

I certainly would not have thought to write a general integer as a2^k+b and then square that instead.

Ok. Some BotE calculations -- just to give you some perspective. A 12M digit number has appr 40M bits. On a 64-bit m/c, that is 625000 64-bit words. To multiply two such numbers by naive n^2 multiplication would take (625000^2 = 4e11) "64x64=128" multiplications. [You can halve that for squaring, but let's just go with this] A 2GHz m/c would need (2e9*200*60) clock cycles / 4e11 operations = 60 clock cycles / operation to be able to hit your mark. Typical modern processor can do a single "64x64=128" multiplication in under 10 clock cycles. So that leaves enough head room for the various other operations (like additions, memory writes, etc..) and still comfortably come in under your target. And this is the O(n^2) method.

2012-05-31, 08:38	#65
LaurV Romulan Interpreter Jun 2011 Thailand 2⁶·151 Posts	yeah, whatever, I eliminated the second edit in my former post, as it was false , I was posting before the calculus finished. It took about 15 minutes! grrrr... you can delete it from your post too, as the reference to VBA could be misleading too, for some who cant directly convert from pseudocode/pascal to vb). I would however keep the link, as the document is quite interesting for some beginner who wants to start experimenting with this. edit, in fact it makes no sense to include the whole text when you reply to the last post...(and it is not really polite, and not very cautious too, guys like me use to edit their last post many times, from English reasons, stupidity, tendency to boast, etc. hehe) Last fiddled with by LaurV on 2012-05-31 at 08:50

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Let GPU72 Decide and other questions	jschwar313	GPU to 72	11	2016-10-14 19:16
Let GPU72 decide	Chuck	GPU to 72	51	2014-09-16 12:49

2012-05-31, 02:10	#59
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 19×397 Posts	Mr. Bobrecki has responded. He has no objections to sharing factoring data. At first we'll probably use our respective web pages that query our databases. If you have any recommendations for him to make that easier, let us know. I'm tempted to make BloodIce our official mers@home DB query manager :) I've also pointed him to Oliver's CUDA code, so he may contact TheJudger at some point.

2012-05-31, 05:25	#60
cheesehead "Richard B. Woods" Aug 2002 Wisconsin USA 2²×3×641 Posts	Will some mod please change this thread's title to "Brainstorming ways to cooperate with Mersenne@home"? I think that would be more suitable than my original title, since it's apparent by now that Mr. Bobrecki is open to a cooperating agreement and has no intention of competing.