[AdamSpeight2008]

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

Spoiler

See me Poly-linguistic, it uses some features C++11.

Spoiler

// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <set>

int _tmain(int argc, _TCHAR* argv[])
{
	auto xs = set<double>();
	for(double x=2; x<=100;x++)
	{
		for(double y=2; y<=100;y++)
		{
			xs.insert(pow( x, y));
		}
	}
	auto c=xs.size();
	auto total = 0;
	// Count 
	for(auto it=xs.begin();it!=xs.end();it++)
	{total += 1;
	}
	cout << c;
	return c;
}

Commentary

Spoiler

Damn you case-sensitive, damn you to hell.
C++ is picky.
Why no .Count? God I miss LINQ's extension methods.

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

[ishkabible]

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 , not a more clever solution

adam:

Spoiler

*REAL* C++ programing uses algorithms for loops

#include <iostream>
#include <set>
#include <iterator>
#include <algorithm>
#include <cmath>

int main() {
	std::set<double> s;
	int x = 100, y = 100;
	for(auto a = 2; a <= x; ++a) {
		auto b = 2;
		std::generate_n(std::inserter(s, s.end()), y - 1, [&]() {
			return pow(a, b++);
		});
	}
	std::cout<<s.size()-1;
	return 0;
}

still; this isn't a very good solution.

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

[AdamSpeight2008]

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



Is it?

[jon.kiparsky]

ishkabible, 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.

[ishkabible]

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

duaaaaa, adam

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

[jon.kiparsky]

ishkabible, 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

   int x = 100;
   int y = 100;
main()
{

   int a = 0; int b = 0;

   int total = 0;

   for (a =2; a <=x; a++)
   {
      for (b = 2; b <=y; b++)
      {
         int lf = least_factor(B)/>;
         if (lf < 0 || (pow (a, lf) > x))
           total ++;
      }
   }
}

where least_factor returns the lowest number that divides b evenly, or -1 if prime

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.

[ishkabible]

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

[jon.kiparsky]

Not hard to get.

Spoiler

If b== i*j, then a ^ b == (a ^ i)^j. If a ^ i is in range, then we're going to count a^b later, so don't count it now. On the other hand, if a ^ i is greater than x, this term will not be duplicated. (example: x=y=5, a=b=4 - for a higher x, 4^4 = 16^2, so it's a dup, but 16 > 5, so it's not a dup, so count it) We only need to look at the first factor of b to decide this (proof left as an exercise...) And if b is prime, then we're not going to find a duplicate, so count it. Works a treat, except in cases like 27^4 == 81^3, where there's a lot of math or a lot of storage required to detect the duplicates.

[ishkabible]

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

[sepp2k]

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

[AdamSpeight2008]

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

[ishkabible]

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

[sepp2k]

AdamSpeight2008, 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.

ishkabible, 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

[sepp2k]

ishkabible, 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

[ishkabible]

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 night

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