Challenge: how many distinct terms in the sequence

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

36 Replies - 24165 Views - Last Post: 12 June 2012 - 04:36 PM

#16 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2251
  • View blog
  • Posts: 9,433
  • Joined: 29-May 08

Re: Challenge: how many distinct terms in the sequence

Posted 26 May 2012 - 04:41 AM

OK if you insist it being preferably written in C++, then here you are.
Spoiler

This post has been edited by AdamSpeight2008: 26 May 2012 - 04:43 AM

Was This Post Helpful? 0
  • +
  • -

#17 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Challenge: how many distinct terms in the sequence

Posted 26 May 2012 - 12:05 PM

jon: ya, my solution has the same bottle neck. I bet you found a similar solution ;)

adam, the .size() method is what you want; why is that loop even their?. also "#include "stdafx.h"" and _tmain are non standard. to boot, that's the same solution as before :P, not a more clever solution

adam:
Spoiler


still; this isn't a very good solution.

This post has been edited by ishkabible: 26 May 2012 - 12:35 PM

Was This Post Helpful? 1
  • +
  • -

#18 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2251
  • View blog
  • Posts: 9,433
  • Joined: 29-May 08

Re: Challenge: how many distinct terms in the sequence

Posted 26 May 2012 - 10:52 PM

ishkabible .size it's not like the intellisense gives you an clue

Attached Image

Is it?

Attached Image
Was This Post Helpful? 0
  • +
  • -

#19 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7621
  • View blog
  • Posts: 12,849
  • Joined: 19-March 11

Re: Challenge: how many distinct terms in the sequence

Posted 26 May 2012 - 11:08 PM

View Postishkabible, on 26 May 2012 - 02:05 PM, said:

jon: ya, my solution has the same bottle neck. I bet you found a similar solution ;)


I don't see a neat way around it, but I see a way to deal with it. I'm having a different problem just now, which suggests that my algorithm, though neat, isn't quite correct, and maybe can't be correct. I might have to back up and rethink. I might be coming at it from the wrong end.
Was This Post Helpful? 0
  • +
  • -

#20 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Challenge: how many distinct terms in the sequence

Posted 26 May 2012 - 11:14 PM

you should post your idea in spoiler tags just cuz I'm curious ;)

edit:
adam: C++ programers don't use intelisense...also that's showing you an implementation detail that makes perfect sese. std::set is almost always implemented as a self balancing binary tree and so are std::map, and std::multimap. they have an extremely common implementation so creating 1 _Tree class that accepts all the right templates and creating a typedef for each one makes perfect sense :P

duaaaaa, adam :P

but ya, that kinda sucks for documentation. I almost always just use my browser for documentation.

edit2:
I wonder how if they use policy based design to get the enriched interfaces that map and multimap provide...I bet that's what that 'false' template argument is for; not really a policy but same idea.

This post has been edited by ishkabible: 26 May 2012 - 11:22 PM

Was This Post Helpful? 0
  • +
  • -

#21 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7621
  • View blog
  • Posts: 12,849
  • Joined: 19-March 11

Re: Challenge: how many distinct terms in the sequence

Posted 26 May 2012 - 11:29 PM

View Postishkabible, on 27 May 2012 - 01:14 AM, said:

you should post your idea in spoiler tags just cuz I'm curious ;)



Basically, it's this:
Spoiler


The problem is that this doesn't understand that for example (3^4)^3 == (3^3)^4, and 27 and 81 are both in range, so it's overcounting. So I'm thinking maybe turning it around somehow, but I don't see exactly how yet. Or else I could complicate it, but I want it to be a nice answer.
Was This Post Helpful? 1
  • +
  • -

#22 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Challenge: how many distinct terms in the sequence

Posted 26 May 2012 - 11:53 PM

if your idea works out that is way better solution than mine; mine is log(X*Y) times slower than yours and yours only uses up constant memory where mine uses up a lot. I don't exactly understand the principals behind yours however :/

edit: also, when I run that code it under counts for me :/


nvm, I copied it wrong.

This post has been edited by ishkabible: 26 May 2012 - 11:57 PM

Was This Post Helpful? 0
  • +
  • -

#23 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7621
  • View blog
  • Posts: 12,849
  • Joined: 19-March 11

Re: Challenge: how many distinct terms in the sequence

Posted 27 May 2012 - 12:07 AM

Not hard to get.
Spoiler

Was This Post Helpful? 2
  • +
  • -

#24 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Challenge: how many distinct terms in the sequence

Posted 27 May 2012 - 12:19 AM

that perfect makes sense! that qualifies as "clever" I'd say ;) I'm going to have to see if I can figure that out now :P
Was This Post Helpful? 0
  • +
  • -

#25 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2100
  • View blog
  • Posts: 3,197
  • Joined: 21-June 11

Re: Challenge: how many distinct terms in the sequence

Posted 27 May 2012 - 12:21 AM

I'm still having trouble with the fact that Adam's solution works. Can someone with a bit of math knowledge explain to me why? Is there some mathematical rule that we can use to show that all different numbers of the form a^b must be far enough apart to be unaffected by floating point inaccuracies? Or is it just sheer luck that it works?

The reason why I'm surprised is that there definitely are numbers of the form a^b that are only one apart (for example 2^3 = 8 and 3^2 = 9 = 8+1) and there are (lots of numbers) between 2^53 and 100^100 such that using doubles x == x+1 would be true. I don't see why there can't be any numbers greater than 2^53, such that both x = a^b and x+1 = c^d for some a,b,c,d > 1.

This post has been edited by sepp2k: 27 May 2012 - 12:22 AM

Was This Post Helpful? 0
  • +
  • -

#26 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2251
  • View blog
  • Posts: 9,433
  • Joined: 29-May 08

Re: Challenge: how many distinct terms in the sequence

Posted 27 May 2012 - 12:33 AM

It has to be something to do with using whole numbers and not fractional one.


Edit:

Quote

I'm still having trouble with the fact that Adam's solution works.

Or are you having hard time accepting that some vb.net programmers know their shi stuff?

This post has been edited by AdamSpeight2008: 27 May 2012 - 12:38 AM

Was This Post Helpful? 0
  • +
  • -

#27 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Challenge: how many distinct terms in the sequence

Posted 27 May 2012 - 12:35 AM

it seems to me that 2^55 or greater should fail...I'm really am just not sure how that works.

2^56 == 4^28 so if by some magic someone can explain how pow(4.0, 28.0) == pow(2.0, 56.0) then you have your answer I'd say

it probably has something to do with how the values are represented; as a base and an exponent so whole numbers to the power of whole numbers work up to much larger values...but I'm not sure.


it all works out somehow; 2^56 == 4^28 == 16^14 == 256 ^ 7

I'm pretty sure whole numbers less than some number K to the power of 1023(maybe like 512, not sure) can be represented perfectly. I think K is greater than 100 by a good bit.

This post has been edited by ishkabible: 27 May 2012 - 12:41 AM

Was This Post Helpful? 0
  • +
  • -

#28 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2100
  • View blog
  • Posts: 3,197
  • Joined: 21-June 11

Re: Challenge: how many distinct terms in the sequence

Posted 27 May 2012 - 12:41 AM

View PostAdamSpeight2008, on 27 May 2012 - 09:33 AM, said:

It has to be something to do with using whole numbers and not fractional one.


Both 2^53 and 2^53+1 are whole numbers. However pow(2,53) == pow(2,53) + 1 is true when using IEEE double precision numbers. So clearly whole numbers in the given range are affected by floating point inaccuracy.

Quote

Edit: Or are you having hard time accepting that some vb.net programmers know their shi stuff?


No.


View Postishkabible, on 27 May 2012 - 09:35 AM, said:

it seems to me that 2^55 or greater should fail...I'm really am just not sure how that works.

2^56 == 4^28 so if by some magic someone can explain how pow(4.0, 28.0) == pow(2.0, 56.0) then you have your answer I'd say


pow(a,b) == pow(c,d) will always return true if the resulting numbers are really equal. What I'm talking about is a case where the resulting numbers should not be equal, but == still returns true.

Quote

it probably has something to do with how the values are represented; as a base and an exponent so whole numbers to the power of whole numbers work up to much larger values...but I'm not sure.


Obviously any powers of 2 can be represented without problem. But for example 2^53+1 will be equal to 2^53 using doubles. So all I'm asking is why aren't there two whole numbers a,b such that a^b = 2^53+1 for example?

This post has been edited by sepp2k: 27 May 2012 - 12:43 AM

Was This Post Helpful? 0
  • +
  • -

#29 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2100
  • View blog
  • Posts: 3,197
  • Joined: 21-June 11

Re: Challenge: how many distinct terms in the sequence

Posted 27 May 2012 - 12:49 AM

View Postishkabible, on 27 May 2012 - 09:35 AM, said:

I'm pretty sure whole numbers less than some number K to the power of 1023(maybe like 512, not sure) can be represented perfectly. I think K is greater than 100 by a good bit.


Whole numbers up to 2^53 can be represented perfectly. After that every number will at least be equal to either its successor or predecessor.

This post has been edited by sepp2k: 27 May 2012 - 12:50 AM

Was This Post Helpful? 0
  • +
  • -

#30 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Challenge: how many distinct terms in the sequence

Posted 27 May 2012 - 12:49 AM

Quote

pow(x,y) == pow(c,d) will always return true if the resulting numbers are really equal.


whatever proof gave you that answer, I would think allows this to happen. I wasn't aware that that was a true statement but what ever reasoning allows for that gives the answer to your question.


nvm, you want a case where pow(x,y) == pow(c,d) even though it's not true...yes I have no clue.

edit:
I just realized it's 3:00 AM where I am...I need to go to bed :P night

This post has been edited by ishkabible: 27 May 2012 - 12:53 AM

Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3