« first day (516 days earlier)      last day (4436 days later) » 

11:01 PM
@JohnSmith oh, you need to make your vector static, or pass it down as argument, or have it as member in a class
 
@JohnSmith the point of memoization is get O(1) time for later calls. if the vector does not persist between calls, then the gain is lost.
 
@JohnSmith what are the first values? F(2) = 2?
@CheersandhthAlf pft. Guess what I forgot to do :/
ideone.com/WBJ5X could be optimized, but it runs. Also, I think there's an error.
anything above 33! returns 0.
hmm, does google not do modulo?
 
@MooingDuck it looks technically OK except for the types. use double for the results. and i would use int for the arguments.
the last result is modulo 2^32 i think.
 
@CheersandhthAlf he said he's using modulo, I'd guess it's modulo (2^32) to make it so we can use unsigned as a type
 
11:12 PM
>>> math.factorial( 16 ) % 2**32
2004189184L
>>> _
 
why not long long to be safe?
 
@JohnSmith because I don't know what euler requires, I made the assumption it wants modulo (2^32)
 
it is modulo 50 millionth prime
 
982451653
projecteuler.net/problem=374 the exact question
i dont know how to set up my facctorial function lol
do I check for n=1 condition and then check for size?
the order of this stuff is tripping me
 
11:18 PM
@JohnSmith yeah, that takes more math than I have. I would fall back on arbitrary arithmetic
 
i am close to the solution on that one but i need a faster factorial function
 
@JohnSmith if you're using a vector, initialize it with the first two values, and then you don't need any special checks.
@JohnSmith wait, that problem is partitions, why are you doing factorials?
 
#include <iostream>
#include <vector>
using namespace std;

static vector<long long> cache;

long long factorial(long long n){

if (n>cache.size()){
return n*factorial(n-1);
//how to cache?
}
}

int main(){
cache.push_back(1);
cache.push_back(1);
cout << factorial(10);

return 0;
}
sorry if that takes up room (is there a better way?)
Mooing Duck: The solution involves factorials
 
@JohnSmith ideone.com
@JohnSmith for how to cache: push the value onto the back of the vector. This works because you know this value has not been cached yet, and by the time it gets to that line, you know it has already cached the next smaller value. So you know that the position for the new value is exactly at the end, every time
 
long long factorial(long long n){

if (n>cache.size()){
cache.push_back(n*factorial(n-1));
}
return cache[n];
}
like this?
 
11:23 PM
@JohnSmith yes
 
not quite
but almost
 
gives me wrong answer though
 
@CheersandhthAlf oh, whoops, not quite, I overlooked the mistake >.<
 
one way to analyze, is to think about one concrete situation
say, vector size 2
 
@JohnSmith do you have a debugger?
 
11:24 PM
and argument 2
what happens?
 
i don't understand
i pushed back 1 and 1
for n=0 and n=1 right
array indices 0 and 1 respectively
 
okay, let's start with the most fundamental eror: that you do not have a base case for the recursion
in @mooing's code that base case was provided by two initial values in the vector: v[0] = 1 and v[1] = 1
 
@CheersandhthAlf he does if he initializes two values in the vector
 
but i mean eventually n=cache size right?
isn't that the base case?
the whole point of pshing back 1 and 1
 
You can specify those in the vector declaration:
vector<long long> cache( 2, 1 ); // 2 elements, each initialized to 1
 
11:30 PM
cache[0] and cache[1] output 1 and 1 correctly
so i don''t think this is the issue
 
it is just by chance
 
oh interesting
apparently pushing back 1 and 1
make my size 2
makes sense
 
@JohnSmith yes, there are two elements in the vector
 
i was assuming it'd do 0 and 1 = size 1
i need to subtract one
 
then if you have fixed that?
 
11:31 PM
there we go
it works now
 
Am I reading this correctly? C++11 doesn’t provide a std::hash specialisation for std::tuple?
 
@KonradRudolph I valuely recall that being the case
C++11 only provided specializations for some wierd types
I have an answer or two somewhere that list them
 
hmm, providing this specialisation would be kind of obvious, is all
 
@KonradRudolph ouch
 
@MooingDuck Ah, just found your answer pertaining to this: stackoverflow.com/a/7111460/1968
 
11:33 PM
2
A: Are there no specializations of std::hash for standard containers?

Mooing DuckNot an answer, but some useful information. The Feb draft of the C++11 standard specifies that std::hash is specialized for these types: error_code § 19.5.5 bitset<N> § 20.5.3 unique_ptr<T, D> § 20.7.2.36 shared_ptr<T, D> § 20.7.2.36 type_index § 20.13.4 string § 21.6 u16stri...

@KonradRudolph the only pointers specialized are unique_ptr, shared_ptr, and vector<bool, Allocator>. Oh, and bitset
 
@JohnSmith have you tried a single call with argument 3?
 
yes
ARGH this fails for the full thing though
i don't think it likes millions-long vectors
or maybe it's millions=-long recursion
gotta increase stack size maybe
 
@JohnSmith or rewrite it to not use recursion
 
can i still memoize it without recursion?
 
@JohnSmith sure.
 
11:39 PM
@MooingDuck Unfortunately your code doesn’t work … is there a concise way in C++ to construct an n–1-adic tuple from an n-tuple, using the second through last values?
 
hw would i change my current code
while n>vector.size or something?
 
@JohnSmith and followed by a call with argument 4? which should produce 24?
 
@JohnSmith replace cache.push_back(n*factorial(n-1)); with a loop instead of calling itself
 
stupid question
 
outputs 6 then 24
 
11:41 PM
@KonradRudolph oh good, I wasn't looking forward to turning my brain on to think about that
@JohnSmith please move your code to ideone.com and paste a link here
 
@MooingDuck Hmm, it should be easy, given how tuples are constructed. But my brain is mush now, I’ll come back to this problem some other day.
 
errr, yes :P
no
 
@JohnSmith how are you planning on addressing the modulo issue?
 
11:44 PM
i just want to get the nonmodulo version working first
then i can just do modulo in each index later
how do i make this iterative?
do i do while n>size loop?
 
for(something; something; something) {
    dosomething;
}
 
@john the problem isn't the recursion, but that you overflow the long long range. i think.
 
i don't think so, my n values are huge
which are going to try to recurse millions of times
i had this problem before on another PE problem
it blows up when i recurse too deeply
 
@JohnSmith btw, long long can't hold factorials bigger than 20!
 
11:48 PM
i don't need it to
i am testing smaller factorials for now
when they work I will pop in the modulus
 
@JohnSmith ok
 
and it should work fine for long long
 
google won't calculate factorials bigger than 170! (which is 306 digits)
 
ok i think i got it
what do you think
 
no
you're just adding to the vector every time
you should have a code path which checks if it is already there
no, wait, my mistake, I misread your loop
looks good to me
 
11:56 PM
@JohnSmith now for the hard part
 
running my PE code now
fingers crossed
 
wait, I just realized, the modulo part is easy. I was thinking you needed the upper bits, now the lower bits :/
I feel silly
 
nooooooooooooooooooooo
wrong answer
bollocks
 
you've got some off-by-one errors, I think
 

« first day (516 days earlier)      last day (4436 days later) »