• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • Paul Clapham
  • Devaka Cooray
  • Bear Bibeault
Sheriffs:
  • Junilu Lacar
  • Knute Snortum
  • Liutauras Vilda
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Piet Souris
Bartenders:
  • salvin francis
  • Carey Brown
  • Frits Walraven

Sum of 1 to 1 000000

 
Ranch Hand
Posts: 37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi everybody,  i need to write a program to calculate the sum of the numbers from 1 to 1,000,000 (including 1 and 1,000,000),but omitting the numbers which are divisible by three and the numbers whose hundred place digit is 2 or 3.

I  have write the code below:



Is there a way to optimize the code?Also at first,i have choose a int for the sum, but the result was a negative number, why that? It is because of the limitation of the integer?  

Thank you
 
Saloon Keeper
Posts: 21981
150
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A famous mathematician whose name I forget was once punished for being too smart for his own good by being assigned the task of adding up all numbers from 1 to 1000 or so. He solved it in minutes by noting that 1+999 = 2+998 = 3.997 ... and thus - if my math is correct - the sum was simply (1000/2) * 1000.

That solution is probably why your own excercise has those extra little qualifications, lest you do likewise. However, I would not be surprised to see a similarly exploitable pattern in this app, since if you apply a rule based on math, there's probably a way to optimise it in math.

I'm not sure what "the numbers whose number of one hundred place is 2 or 3" means in English, though.
 
Steven Desilets
Ranch Hand
Posts: 37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:A famous mathematician whose name I forget was once punished for being too smart for his own good by being assigned the task of adding up all numbers from 1 to 1000 or so. He solved it in minutes by noting that 1+999 = 2+998 = 3.997 ... and thus - if my math is correct - the sum was simply (1000/2) * 1000.

That solution is probably why your own excercise has those extra little qualifications, lest you do likewise. However, I would not be surprised to see a similarly exploitable pattern in this app, since if you apply a rule based on math, there's probably a way to optimise it in math.



Thank for your answer

Tim Holloway wrote:I'm not sure what "the numbers whose number of one hundred place is 2 or 3" means in English, though.



Maybe, hundred place digit, ten place digit,one place digit? Not sure
 
Tim Holloway
Saloon Keeper
Posts: 21981
150
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm going to guess that that last means numbers whose 100's place is 2 or 3, Thus, 200-299, 300-399, 1200-1399, 2200-2399...

You can obviously short circuit 200 additions by subtracting the sum 200...399 from the 1-1,000,000 (excepting multiples of 3) total and do likewise for each of the other blocks. You can probably compact the summing of the other blocks as well, if you're creative.

 
Rancher
Posts: 3507
37
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The mathematician in question was Carl Friedrich Gauss.  I recall a teacher asked me a similar question when I was 11, and I found the same solution Gauss did.  Unfortunately I did not go on to have a litany of discoveries and formulas named after me the way Gauss has.  Seriously, that guy did a lot.

As far as optimizations... well there's a very basic one, don't calculate (i/100)%10 twice in a row; once should be enough.  As far as more clever tricks... well you can use Gauss' formula (n*(N+1)/2) to calculate the full sum for 1 to N, then subtract the sum for all multiples of 3 (which probably has a similar simple formula), and then also subtract the values where the hundreds place is 2 or 3, but i is not also a multiple of 3 (don't count those twice!).  That last part may still require a loop, but it should be possible to make it a smaller loop...
 
Tim Holloway
Saloon Keeper
Posts: 21981
150
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Note the "gotcha". If you eliminate 303 because it's a multiple of 3, you also have to have eliminated it from the "sum of 200-399" sub-formula!
 
Steven Desilets
Ranch Hand
Posts: 37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for your answer
 
lowercase baba
Posts: 12831
52
Chrome Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:if my math is correct - the sum was simply (1000/2) * 1000.


sorry.  As a former math teacher, I have to tell you your math is NOT correct.  you're fine until you get to the middle...you can have 499 + 501, but then what do you add to 500 to get 1000?

Gauss actually had to sum 1 - 100, and did 100 + 1, 99 + 2, etc, down to 50 + 51, giving him 50 pairs totaling 101, so the forumula is (n)(n + 1)/2, or 5050.  for 1 to 1,000,000 , it would be (1,000,000)(1,000,001)/2, or 500,000,500,000

Sorry.

as to "Is there a way to optimize the code?"  I would say "Don't".  There's no need to. i'm pretty sure this code would run pretty dang fast.  Unless you have SPECIFIC and DOCUMENTED timing requirement, you're always better served writing clean, simple code that's easy to understand.  When you go back to it in a week or a month (or in my case, an hour), you don't want to have to struggle to figure out what the heck you did...

Personally, i'd break up your test into individual conditions. that way they are easier to change later. something like


I might even put each condition into its own method, in case the specs change and things get a bit more complicated.
 
Steven Desilets
Ranch Hand
Posts: 37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I forget to ask, but why choose double over integer for the sum?
Thank
 
fred rosenberger
lowercase baba
Posts: 12831
52
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Carey Brown wrote:Typo (it's so easy to do)
keepit == false;


yeah, that's what I get for writing it on the fly, not testing, and flipping around between different languages.

and being lazy.  

to be clear, most of what i wrote should have had

keepit = false;//single '=' for assignment
 
Marshal
Posts: 68936
275
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Steven Desilets wrote:. . . Is there a way to optimize the code? . . .

Yes, of course there is. You use n × (n + 1) ÷ 2. That is probably not what you are supposed to do if this is a test of your ability to write loops.

. . . Also at first,i have choose a int for the sum . . .

As Fred has shown, you will overwhelm the range of an int (−2147438648…2147483647 (inclusive)), to which the answer is to declare sum as type long, not double. A long has a range with 19 digits starting 922..... You have now seen what an overflow error looks like.
 
Mike Simmons
Rancher
Posts: 3507
37
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Steven Desilets wrote:. . . Is there a way to optimize the code? . . .

Yes, of course there is. You use n × (n + 1) ÷ 2. That is probably not what you are supposed to do if this is a test of your ability to write loops.



Well, it also has has the issue of being wrong. ;)
 
Steven Desilets
Ranch Hand
Posts: 37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Steven Desilets wrote:. . . Is there a way to optimize the code? . . .

Yes, of course there is. You use n × (n + 1) ÷ 2. That is probably not what you are supposed to do if this is a test of your ability to write loops.

. . . Also at first,i have choose a int for the sum . . .

As Fred has shown, you will overwhelm the range of an int (−2147438648…2147483647 (inclusive)), to which the answer is to declare sum as type long, not double. A long has a range with 19 digits starting 922..... You have now seen what an overflow error looks like.



Thank now i understand.
 
Saloon Keeper
Posts: 3900
154
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would not try to be clever here, just a simple brute force. The only thing I would change is the for-loop, like:
 
Piet Souris
Saloon Keeper
Posts: 3900
154
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes!!! Off by one error, was a long time ago! Should be: i += i % 1000 == 199 ? 201 : 1
 
Sheriff
Posts: 15527
263
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:I would not try to be clever here, just a simple brute force. The only thing I would change is the for-loop, like:


I think you failed at trying not to be clever—that increment clause is pretty clever.

Yes!!! Off by one error, was a long time ago!


Edit: And I see it bit you anyway  
 
Tim Holloway
Saloon Keeper
Posts: 21981
150
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

fred rosenberger wrote:
as to "Is there a way to optimize the code?"  I would say "Don't".  There's no need to. i'm pretty sure this code would run pretty dang fast.



Not THAT fast! It's making a million passes. It's only fast because modern machines are fast. Certainly Gauss' formula (and thanks for giving the correct version!) is a LOT faster if the range of numbers to be summed exceeds about 20 or so.

I actually got tripped up on this once doing Black-Scholes probability trees. Each individual operation was simple, but there were so many of them. Once I combined the commonalities I got what our finance expert said was the fastest implementation he'd ever seen. And he actually had a proprietary copy as a reference. We just had to re-create it for legal reasons.

On the other hand...

fred rosenberger wrote:Unless you have SPECIFIC and DOCUMENTED timing requirement, you're always better served writing clean, simple code that's easy to understand.  When you go back to it in a week or a month (or in my case, an hour), you don't want to have to struggle to figure out what the heck you did...

 
Campbell Ritchie
Marshal
Posts: 68936
275
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Mike Simmons wrote:. . . Well, it also has has the issue of being wrong. ;)

When did I ever let things like being wrong bother me  ?
You can calculate the sum of an arithmetical progression to include numbers ending ...2xx and...3xx, as somebody has already said, and you can similarly work out the sum of numbers divisible by 3. But, since this is obviously an exercise in writing loops, I did say that OP wasn't supposed to do that.
 
Steven Desilets
Ranch Hand
Posts: 37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Steven Desilets wrote:. . . Is there a way to optimize the code? . . .

Yes, of course there is. You use n × (n + 1) ÷ 2. That is probably not what you are supposed to do if this is a test of your ability to write loops.

. . . Also at first,i have choose a int for the sum . . .

As Fred has shown, you will overwhelm the range of an int (−2147438648…2147483647 (inclusive)), to which the answer is to declare sum as type long, not double. A long has a range with 19 digits starting 922..... You have now seen what an overflow error looks like.



Well i just test again and the number is not negative, i got this number:

405761115

but since the the max range is 2147483647 , do this number is the result of a integer overflow?





 
Piet Souris
Saloon Keeper
Posts: 3900
154
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I ran this code on my 9 year old laptop with an I3 processor:

And it took under 0.1 seconds. The parallel version took twice as long.
 
Campbell Ritchie
Marshal
Posts: 68936
275
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Steven Desilets wrote:. . .
405761115

but since the the max range is 2147483647 , do this number is the result of a integer overflow?

Yes, that was an overflow error.
 
Steven Desilets
Ranch Hand
Posts: 37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Alright Thank you
 
Mike Simmons
Rancher
Posts: 3507
37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet's code inspired this response:

For MAX_NUM of 1_000_000, it's really too fast to measure, either way.  But if you kick it up to, say, 2_000_000_000, you will see a notable difference in performance.
 
Mike Simmons
Rancher
Posts: 3507
37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:But, since this is obviously an exercise in writing loops, I did say that OP wasn't supposed to do that.


On the other hand, since the OP had already solved the problem with a loop, it seems fair to then look at alternatives.
 
Campbell Ritchie
Marshal
Posts: 68936
275
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In that case, I can think of some weirder techniques.
  • 1: The sum of the arithmetical progression (=AP) 0...1,000,000 is 500,000,500,000 as Fred said last night. Slightly over 5×10¹¹
  • 2: The sum of an AP from m...n in steps of k is (m + n) × ((n - m) ÷ k + 1) ÷ 2. All ranges are regarded as inclusive.
  • 3: If m is 0 and k is 1, you are summating consecutive numbers, and the formula in No 2 reduces to n × (n + 1) ÷ 2. If you summate numbers 1...n and use the associative property of ×, you will get the same formula.
  • 4: You can summate numbers in the format ...2xx and ...3xx. The sum of 200...399 is (200 + 399) ×((399 - 200) ÷ 1 + 1) ÷ 2.
  • 5: The sum of 1200...1399 is ((1399 - 1200) ÷ 1 + 1) × 1000 more than the sum of 200...399. The sum of 2200...2399 is more by that formula but ending ...× 2000. And you can continue until you get a formula ending ...× 999,000. You now have an AP of APs which you can calculate readily with the usual formula. Subtract that from the 500,000,500,000.
  • Numbers divisible by 3: see following post when I have written it.
     
    Campbell Ritchie
    Marshal
    Posts: 68936
    275
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    A few minutes ago, I wrote:. . . see following post . . .

    And I can't see it because I have got my screen too small even for me to read.

    There are two hundred numbers divisible by 3 in the following ranges combined: 200...399, 1200...399, and 2200...2399. Two of the ranges have 67 and one has 66. Summate the numbers 0...199 (or 1...199, which gives the same result). Work out whether you need to add 0 67× or 66×. Work out whether you need to add 1,000 67× or 66×. Work out whether you need to add 2,000 67× or 66×.
    You now have a total. The total for the combined ranges 3200...3399, 4200...4399, and 5200...5399 is 200 ×3,000 more than that. Repeat that and you get a 333‑element AP which you calculate the total of. You are now missing the range 999200...999399. There is another AP with > 65 elements and < 68 elements in there of numbers divisible by 3. Remember that all integers divisible by 3 have the transverse sum of their digits divisible by 3, and you will find that last AP easier to find. Add the totals of those two APs back and Bob's your uncle.
     
    Piet Souris
    Saloon Keeper
    Posts: 3900
    154
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Interesting, but not easy. And the question is: is it worthwhile? Can you make an implementation?

    I was inspired by Mike's clever use of two LongStreams, getting rid of the modulo 3 business.
    So I thought: why not combine it with my jumps in the index?

    Doing so and comparing the sum with Mike's sum, I noticed that the sums were off, totally off. I spent a lot of time searching for the problem, and finally it became clear that my jump in the index was wrong. I did:

    and that jump is okay when i is 199, 3199, 6199 et cetera, but not when i is 1198. I guess learning modulo arithmatic was a (int) long time ago....

    So I fixed that, and compared running times against Mikes running times.
    For MAX = 1_000_000, Mikes way is faster, but for MAX = 1_000_000_000, my way was 6 times as fast. I looked for mistakes, but couldn't find one. Anyone an idea?

    The code I used was:

     
    Campbell Ritchie
    Marshal
    Posts: 68936
    275
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Piet Souris wrote:. . . is it worthwhile?  . . .

    What has worthwhile got to do with it?
     
    Piet Souris
    Saloon Keeper
    Posts: 3900
    154
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Of course... I apologize for my silly question  
     
    Junilu Lacar
    Sheriff
    Posts: 15527
    263
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I ran all (most?) of the different algorithms through a profiler (Java Flight Recorder) in IntelliJ IDEA:

    These are the results:
    main() - 100% (766 samples)
    streamSum() - 37.6% (288 samples)
    mikeSum() - 23.4% (179 samples)
    ifOr() - 14.9% (114 samples)
    ifAnd() - 13.3% (102 samples)
    pietJump() - 10.8% (83 samples)

    Based on these results, it seems Piet's version is at least twice as performant as a straight up summing with a LongStream but maybe not so much better than the original algorithm posted by OP.
     
    Piet Souris
    Saloon Keeper
    Posts: 3900
    154
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    A bad name for the class....    
     
    Mike Simmons
    Rancher
    Posts: 3507
    37
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Speaking of which, I was surprised when I saw Piet had chosen the same class name I had- I thought it was coincidence, as I had included only the methods, not the class.  But I see I overlooked one reference.
     
    Piet Souris
    Saloon Keeper
    Posts: 3900
    154
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Yes, I noticed the reference... otherwise I would have called it 'AbelsSum'. I learned this trick when I was 11, in primary school, and I seem to recall the teacher mentioned Abels.... well, memory can play tricks on you.
     
    Mike Simmons
    Rancher
    Posts: 3507
    37
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    It appears Niels Abel worked on a more general form of that type of sum.  7-year-old Carl Gauss solved the initial simplest case about 18 years before Abel was born.
    Content minimized. Click to view
     
    Mike Simmons
    Rancher
    Posts: 3507
    37
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    [accidental duplicate]
     
    I like tacos! And this tiny ad:
    Learn to write code others love to read, one example at a time!
    java.by-comparison.com
      Bookmark Topic Watch Topic
    • New Topic