« first day (445 days earlier)      last day (4496 days later) » 

8:00 PM
@StackedCrooked In my top voted answer, the gotcha was that all large allocated arrays happened to have the same modulus over 4096...
 
The subtraction loop usually ends when the current value is less than the divisor. You can't test if a pointer is less than a number.
 
@RMartinhoFernandes In what universe does 0x10 + 4 equal 0x0c? :)
 
@Mysticial don't modulo by powers of two?
 
@FredOverflow Nothing says addresses have to go up when you + on them.
 
@MooingDuck Correct. Usually, the more "prime" the number is, the better.
 
8:01 PM
@sbi No, you can't. If you have a pointer p and start subtracting, you immediately fall into undefined behavior land.
int i = 42;
int* p = &i;
--p;   // undefined behavior
 
thanks
 
@RMartinhoFernandes still undefined behavior
 
@MooingDuck But at least compiles.
:P
 
Well, first it was "does not compile", now it is undefined behavior :)
 
8:03 PM
@Mysticial Does this only apply when hashing pointers (or generally numbers that are likely divisible by a power of two). Or is this is principle that aplies to all hashing?
 
@StackedCrooked all general hashing
 
@Mysticial Because, suppose I need to hash natural numbers then the only thing that matters is how big the seed is. The bigger the better.
 
@StackedCrooked Dividing by prime numbers is always a good idea, if that's what you're asking. So all the bits influence the result.
 
@FredOverflow Suppose I need to hash numbers in [0, 99] range. Are you saying that 13 is a better choice than 15 because it's a prime number?
 
sbi
@FredOverflow Spielverderber!
 
8:04 PM
@StackedCrooked for natural numbers yes, for computers no
 
@MooingDuck Yep that was my previous question.
 
@StackedCrooked If the range is that small, just make a hash table of size 100 and use the identity function.
 
@StackedCrooked from 0 to 99? Not in that case.
 
@FredOverflow I'm trying to illustrate the principle.
 
Note that x % 1013 is the identity function for numbers smaller than 1013.
 
8:06 PM
@StackedCrooked For computers, I'm tempted to think that any n that is odd will work pretty well, since I'm not aware of any computer patterns that would have a periods of anything other than a power-of-two.
 
@FredOverflow So it's the perfect seed.
 
What seed? Are you doing a pseudo random number generator?
 
A pseudo random hash table.
 
@Mysticial really, any number that does not divide evenly into the maximum value, assuming they are evenly distributed. For computers, primes work very well
 
Primes are awesome.
 
8:07 PM
@FredOverflow I'm not sure if seed it the right word here.
 
The only prime that doesn't work well is 2 ;)
 
@StackedCrooked it's not
@FredOverflow have we decided that 1 is not a prime? Or do we just ignore it and make it neither prime nor not prime?
 
@MooingDuck The source code of std::hash uses: size_t __seed = static_cast<size_t>(0xc70f6907UL))
 
sbi
@FredOverflow Prima ballerinas are awesome. Primes are dull.
 
@MooingDuck 1 is not prime in my universe, because otherwise your factorizations wouldn't be canonical anymore.
 
8:08 PM
Things work best if 1 is not prime.
 
@StackedCrooked who's source code? Dinkum? GCC-whatever-it-is?
@FredOverflow makes sense
 
If 1 is prime, pretty much every thing about primes you come up with you need to special case 1.
 
1 would be useless as a prime factor.
@MooingDuck gcc 4.6
 
@sbi "Prime ballerina" sounds like a female who is good at Quake and stuff :)
 
It's easier to just special case 1 away from the start.
 
8:09 PM
@MooingDuck Correct. Though from the performance side, you have to play games. Once thing to notice is that the "better" the modulus for hashing, the slower it tends to be for the actual division modulus step itself.
 
@StackedCrooked wonder why that number. doesnt seem to be prime
 
@Mysticial I thought modulus was all the same speed except powers of two
 
Division algorithms (in both hardware as well as compiler optimizations) will give better speed to small or highly composite numbers.
 
@sbi lol didn't notice that at first :)
 
8:10 PM
@MooingDuck Not true, try a division by 3 and look at the assembly. The compiler doesn't do a division at all.
 
@Mysticial alright, division by a variable. As per previous post, didn't know that. Interesting
@RMartinhoFernandes I figured out it wasn't prime, that's why I said so.
 
@Mysticial If I were a compiler, I would probably replace division by 3 with multiplication by 1431655765 and then use edx.
 
@MooingDuck And if you look at the Intel documention for both their integer and floating-point division functions, it says that the latency is lower when the divisor is short or round.
 
@Mysticial neat
 
8:13 PM
@FredOverflow Correct, and that's exactly what it does. :)
 
Really, verbatim? No rounding correction or funny corner cases?
 
@FredOverflow If so, you would be an x86-specific compiler.
 
@FredOverflow Now if you can figure out the math behind why it's valid... :)
 
1431655765 * 3 is roughly 2^32
 
1431655765 *3 is the 32bit zigamorph?
 
8:16 PM
Is he Zoidberg's cousin or something?
 
@FredOverflow Yep. The hard part is proving that the "roughly" is close enough to never be wrong.
 
I assume "taking edx" means taking only the higher 32-bits of a 64-bit result?
 
I can't figure out how MSVC's hashtable works :( I see no hashing function. I should look in the standard.
 
> Unicode is a 16-bit character code
 
Shoot him.
 
8:18 PM
The same "multiply by reciprocal" trick can be used for a lot of small divisors. For larger divisors, it doesn't work because of round-off. In those cases, the compiler may try to factorize the divisor and do each one individually...
And I just got my first downvote in 40 days... great...
 
Solving equations with integral division is fucked up.
 
huh, MSVC9's std::hash_compare does..... Qrem = hash_value of the parameter, modulo LONG_MAX, divided by 127773. Then returns 16807*Qrem.rem- 2836*Qrem.quot. Then it clamps between 0 and LONG_MAX. Huh.
 
@CatPlusPlus Oh, that's from the Jargon File. It's likely outdated as heck. Probably from the days of UCS-2 or something. Or just plain wrong.
 
@Mysticial According to a simple test program, it fails for every multiple of 3 :)
 
@Mysticial You haven't been controversial enough.
 
8:23 PM
@FredOverflow Check what the compiler does exactly, it probably has some cleanup code somewhere.
@CatPlusPlus Probably...
1
A: What is overalignment of execution regions and input sections?

MysticialOveralignment is when the data is aligned to more than its default alignment. For example, a 4-byte int usually has a default alignment of 4 bytes. (meaning the address will be divisible by 4) The default alignment of a datatype is quite-often (but not always) the size of the datatype. Overalig...

In this case both my answer and the accepted answer got downvoted... so...
 
I usually get downpoos on singleton answers.
Which means they're working.
 
<whinemode>If I don't pick up another 6 upvotes, my rep won't be divisible by 5 anymore</whinemode>
lol
 
:)
 
@Mysticial Downvote someone then.
 
8:27 PM
lol
 
floor(x * 1431655765 / 2^32) = floor(x / 3) Need help with floor. How the heck do I get rid of it in the equation?
 
@RMartinhoFernandes Are you trying to work on the proof?
 
@Mysticial Yes.
 
@Mysticial Yes. First of all, it uses negative 1 billion, and then it also adjusts an intermediate result by some rounding correction stuff.
 
I might be down a wrong path, but I still want to know how I can handle floor.
 
8:29 PM
@RMartinhoFernandes You can't.
 
floor() is indeed the wrong way to approach it. The way is to use error-bounds
 
floor is a lossy operator- you can't go from floor(x) to x
 
this might actually be a good question to put on math.SE
though I don't have an account there
 
@RMartinhoFernandes You don't need to prove it, I already disproved it :)
 
@DeadMG x is an integral.
@DeadMG I can solve the equation floor(x / 2) = 5 for example.
 
8:30 PM
so in other words, both of the floor calls are useless, since integer division is already defined to truncate
 
x is in { 10, 11 }.
@DeadMG Well, that just shifts the question to "How do I handle integral division".
 
@RMartinhoFernandes That's not a solution, it's several
 
@DeadMG Equations can have more than one solution.
 
Anyway, for hashing purposes, it doesn't matter at all if our hashing function divides by 3 exactly.
 
8:31 PM
yes, I know that much
but you can only go from floor(x) to x if you know what x is
so fundamentally, you did not regenerate the value of x at all
 
Actually, my compiler uses 1431655766 instead of 1431655765
 
you merely pointed out that you knew what it could be
 
@DeadMG That's the solution.
 
so it purturbs it up by 1 to make it truncate correctly
 
8:33 PM
no, it's not the solution, because you gave more than one value
 
@DeadMG He already said that floor(x / 2) = 5 (in the mathematical sense!) means x is either 10 or 11.
 
you only said what it might have been, not what it was
 
If you want, I'll state everything: floor(x / 2) = 5 and x is a natural number
 
then that's a solution for N
but x != N
 
4 mins ago, by R. Martinho Fernandes
@DeadMG x is an integral.
 
8:34 PM
yes, I got that far
 
So?
{ 10, 11 } is the set of all solutions.
 
knowing all of the possible values of X does not mean that you know what X was
it merely means that you know what it could not have been
 
What does "what X was" mean?
 
-2
Q: Image moving across screen at the Speed of Light

JuanVelezWould it be possible to write a program that can make an image, lets say a circle the size of a dime, move across your computer screen back and forth at the speed of light having a monitor that is lets say 20 inches wide; if not, then would it be possible to make the image move across the screen ...

 
I'm gonna go play games
 
8:36 PM
lolwat?!?!?!
 
In fact, in my original example, I want the solution to be the all the naturals in [0, 2^32[. I don't want a single solution. That would prove the formula doesn't work for all of them. I want to prove it works for all, so I want to get 0 = 0.
I'm not playing "find the x". I'm "solving an equation", and that means "finding all its solutions".
 
@Mysticial ((i + 1) * 1431655765ULL) >> 32 seems to work fine, except for 0xffffffff :)
 
@FredOverflow I compiled using int (signed), so that's why it works :)
 
unsigned i = 0;
do
{
    unsigned a = i / 3;
    unsigned b = ((i + 1) * 1431655765ULL) >> 32;
    if (a != b)
    {
        std::cout << "oh noes! " << i << ", " << a << ", " << b << "\n";
        return;
    }
} while (++i);
std::cout << "yay!\n";
oh noes! 4294967295, 1431655765, 0
 
8:41 PM
@RMartinhoFernandes "All the naturals"? Don't let Tony read this, it'll make him horny!
 
WTF????
 
10
Q: How do you handle the floor and ceiling function in an equation?

SvishI tried to do some math in a blog post of mine and came to one with a floor function. I wasn't sure how to deal with it so I just ignored it, and then added the ceiling function in my final equation as that seemed to give me the result I wanted. I'm wondering what is the correct way of handling t...

Found a few ideas to handle it here.
 
@FredOverflow Are we talking about tits?
 
@TonyTheLion Is the term "naturals" unfamiliar to you?
 
@RMartinhoFernandes As for the proof for the 1431655766 for division by 3. IIRC, the idea is to use ((x + e1) * 1431655766) / 2^32 = x / 3 + e2 and show that e2 us always less than 1. (I might have the epsilons in the wrong place...)
 
8:42 PM
@EtiennedeMartel Now you spoiled it :)
 
Sorry about it.
 
@Mysticial I was going to try that just now! Second answer in the question I found.
 
@FredOverflow no, but it wasn't a sex reference in @RMartinhoFernandes context, so I didn't think nothing of it
 
Wait, why add the first epsilon to x and not to the result of division?
 
@RMartinhoFernandes I'm not sure if I have them in the right place, or even if 2 were necessary.
 
8:44 PM
Is it intended to make all 32 lower bits zero?
 
It's been a while since I've done a proof like this.
 
@Mysticial I have two floors, so I guess I need two.
I'll try it on paper.
 
@Mysticial I still haven't been able to get my head around that algorithm we spoke about yesterday. If you have any more ideas, let me know
 
No, scratch that. I'm going to have dinner first.
And solve it in a napkin!
Bye.
 
@RMartinhoFernandes Why do you insist on proving a formula that's already been disproved? :)
 
8:45 PM
The last time I did a proof like this was while I was implementing a specialized integer multiply-modulus function.
 
@FredOverflow What's the correct formula then?
 
7 mins ago, by FredOverflow
@Mysticial ((i + 1) * 1431655765ULL) >> 32 seems to work fine, except for 0xffffffff :)
 
@TonyTheLion I don't know either. I've basically told you what I know. That it's a Cooley-Turky (radix 2) and fixed-point. I upvoted your question btw. (and retagged it)
 
@Mysticial oh right, thanks :)
 
@FredOverflow Shouldn't it work always?
 
8:48 PM
@RMartinhoFernandes It "overflows" for the largest value.
 
@Mysticial do you perhaps by any chance understand how the Cooley-Tukey Algo itself works?
 
using 1431655766, 1431655765 is wrong.
@TonyTheLion Yes, it's quite literally, part of my Ph.D thesis...
 
@FredOverflow If I see correctly, it would make ~0 / 3 be 0.
 
@Mysticial With 1431655766, I get oh noes! 2147483648, 715827882, 715827883. A number that doesn't exist for signed integers :)
 
Oh, it's for signed integers only?
 
8:50 PM
@Mysticial right
 
@TonyTheLion Cool Turkey sounds like leftover Sunday.
 
I still see "Cold-Turkey" every time I read that name.
 
Oh wait, the assembly in my compiler has more to it:

mov eax, 1431655766 ; 55555556H
imul DWORD PTR _x$[ebp]
mov eax, edx
shr eax, 31 ; 0000001fH
add eax, edx
 
@FredOverflow Lol.
 
@CatPlusPlus I even know what that means :)
 
8:51 PM
Dammit people will you make your mind?
 
not Turkey but Cooley–Tukey....
 
make mind
 
just saying
 
That's dirty... it does a shift and an add... lolz
 
So if the result is negative, it has to be corrected by subtracting 1.
 
8:52 PM
So, it's (x * 1431655766 >> 32) >> 31 + (x * 1431655766 >> 32)? (using very longs for the magic number)
 
For the unsigned case, it's this:

mov eax, -1431655765 ; aaaaaaabH
mul DWORD PTR _x$[ebp]
shr edx, 1
 
x * 2863311531 >> 32 >> 1?
 
Funny that it uses the negative value.
 
Or is multiplication signed?
 
mul is unsigned
imul is signed
 
8:54 PM
Ok.
 
imul is signed
 
was imul invented by Apple?
 
@TonyTheLion then I guess they also invented idiv
 
unsigned i = 0;
do
{
    unsigned a = i / 3;
    unsigned b = (i * 0xaaaaaaabULL) >> 33;
    if (a != b)
    {
        std::cout << "oh noes! " << i << ", " << a << ", " << b << "\n";
        return;
    }
} while (++i);
std::cout << "yay!\n";
It works! And the program even contains a bull. Can you spot it? :)
 
@Mysticial likely, they have invented ALL THE I-things so far
 
8:56 PM
I bet they even invented the saying: Aye Aye!
 
@FredOverflow lol
 
@FredOverflow a bull? oh
 
I bet you all the Apple get an i put in front of their name, so if I worked there I'd be "iTony"
 
@MooingDuck Yep. Aaaaaaa bull.
 
@MooingDuck Yes, a bull. Have you found it? :)
@RMartinhoFernandes lol
 
8:57 PM
@RMartinhoFernandes Aaaaaa! A BULL!
 
#define BULL NULL
 
Remember iGoogle? Anyone still using that?
 
I google things sometimes.
 
@StackedCrooked I would love the see the lawsuits that would come out of iGoogle...
 
0
Q: In what kind of situation, c++ destructor will not be called?

user1130800In c++, we love to do something in the destructor. But in what kind of situation, destructor will not be called? for examples in the following case: exit() call in the thread, unhandled exceptions and exit, TerminiteProcess() (in windows), warm/cold reboot computer, sudden out of power of comp...

> TerminiteProcess() (in windows), warm/cold reboot computer, sudden out of power of computer...
 
8:58 PM
TerminiteProcess() sounds like a disease
 
Reminds me of "finally blocks don't run if you pull the plug".
 
0
Q: In what kind of situation, c++ destructor will not be called?

user1130800In c++, we love to do something in the destructor. But in what kind of situation, destructor will not be called? for examples in the following case: exit() call in the thread, unhandled exceptions and exit, TerminiteProcess() (in windows), warm/cold reboot computer, sudden out of power of comp...

 
room topic changed to Lounge<C++>: Sudden out of power of computer. [c++] [c++11] [c++-faq]
 
room topic changed to Lounge<C++>: Sudden out of power of computer and it is suck. [c++] [c++11] [c++-faq]
 
8:59 PM
nah, deleted my comment, it wasn't appropriate
 
I'm not deleting mine, 'cause it's awesome.
 
Then I'll add mine back
 
Zombie apocalypse won't prevent destructors from running.
2
Zombies don't eat machines. :P
 
@RMartinhoFernandes That should be a comment. Not an answer. :)
 
Oh, right dinner.
Bye.
 
9:06 PM
Humpf
Insightful comment : 0 votes
Zombie apocalypse : 4 votes
 
Let's fix that. There.
 
My workplace is next to where these guys do their recordings.
I think that's pretty cool :D
 
@StackedCrooked I'm a fan of Soulwax. Where is that ?
 
9:19 PM
Wow, which language is that
 
@kbok Dutch.
 
@CatPlusPlus Seems he's relying on constructors to release remote resources. Hmm.... maybe you should have the remote resource owner ping your process and release if your process doesn't respond.
 
@Xaade how'd you figure that out? Also, "heartbeat" is a common term for that.
 
@MooingDuck I'm psychic. But seriously, this would be a problem. If it's local resources, then it doesn't matter if the process is terminating. However, if it's locking up remote resources, then you could leave the remote resource hanging if you're relying on the destructor.
 
@Xaade yeah. I have something like that in my code, where a temporary file's destructor cleans it's resources, plus those leaked from previous runs. Then I can stop debugging whenever and it still gets cleaned eventually.
@Xaade Yeah, I've been wondering all week what's the proper way to handle that client side. I don't think there's a good answer. I think the server must detect closed connections and release those resources itself. It could be done, but it wouldn't be "good programming"
 
9:30 PM
@MooingDuck if you wanted to handle client side, you could have a service run in the background, but then if the computer up and offs itself, you need the server to release. Having server release it's resource upon the determination that the client is non-responsive is in fact the correct way.
He who owns resource, releases resource.
 
@Xaade on an only vaguely-related note, I dislike that C++ allows destructors to throw exceptions. I have determined that is never the right answer.
 
@RMartinhoFernandes Yeah, that was nice. It saved the clueless answerer from about a dozen downvotes, if you ask me. People were entertained by the comment thread and just missed the non-answer below the fold :)
 
See: Boost.Exception.
 
@CatPlusPlus oh right, you said that last time but I got lost in teh documentation, forgot why I was there, and left
 
At least, AFAIR.
@DeadMG was using throwing destructors for constructing exceptions.
 
9:38 PM
@MooingDuck My mentality is that if you get a fileNotFound when trying to close a file to release the file resource that was held by an object that just met an error and wants to die, the object is already dead. No need to cry over a job already done.
 
I don't know anything anymore.
 
@Xaade in my case, I had an vector of temporary-file objects that should delete their files when the object is destructed. One failed due to a virus scanner, causing the vector to leak all of them. Plus the vector's internals
 
@CatPlusPlus I did but changed it
 
@MooingDuck Boost.Exception is awesome.
 
1 min ago, by Cat Plus Plus
I don't know anything anymore.
qft
 
9:40 PM
Ok, users pay attention: DOWNLOAD = GET - get illegal movies UPLOAD = PUT - put pics of facebook INSTALL = what you always do with malware
 
Those logic lectures are fucking incomprehensible.
 
@CatPlusPlus Why did you keep mentioning Boost.Exception? It's destructor doesn't seem to throw, and I can't figure out what else you could have been implying
 
I don't knooooooooooooooow.
Leave me alone.
 
@StackedCrooked Gibberish. Mr. StackedCrooked attracts gibberish
 
9:45 PM
Maybe he's implying it's awesome.
 
@RMartinhoFernandes maybe it is, I'm still sticking with "C++ destructors should have been nothrow"
 
@MooingDuck In practice they pretty much are.
 
@StackedCrooked but they should be required to be.
 
@CatPlusPlus They're pretty worthless, from my experience
 
@StackedCrooked I dislike the mess added to my containers caused by the fact that Allocator::destroy isn't nothrow
 
9:48 PM
Yeah, I assumed that was what you meant.
 
I have a test in 8 hours.
 
Sometimes I wish I could create a scoped_catch object.
 
@CatPlusPlus Get the fuck to sleep.
@StackedCrooked What's that?
 
I need to at least read this crap.
 
Ah, another sorting problem...
 
9:49 PM
An object you create and catches any exceptions thrown in its scope?
 
@RMartinhoFernandes Yep.
 
I think D has something on that spirit.
 
@RMartinhoFernandes Like a fish net?
 
D has some special scopes.
 
@StackedCrooked also nice would be the ability to stop stack unwinding in a destructor, outside of a catch handler.
 
9:50 PM
Hm..
 
which it just dawns on me would be exactly how one implemented a scoped_catch object.
 
Ah, it's scope(failure) action_goes_here();
 
If you're using pimpl then you actually can stop propagation in the destructor.
 
@MooingDuck Wouldn't that leak things?
 
9:53 PM
@RMartinhoFernandes Why would that leak? It should either handle the exception, or rethrow. Even if it didn't execution would continue after the scope of that object.
 
@RMartinhoFernandes No. Program flow woud continue on in stack frame where the catch occurred.
 
@MooingDuck What happens to destructors that were supposed to run after the one that stopped unwinding?
 
@RMartinhoFernandes they would still be in scope. Why would they be destructed?
 
@MooingDuck What happens to objects that were destroyed before the one that stopped unwinding?
 
@RMartinhoFernandes they're out of scope. Why wouldn't they have been destructed. It would work exactly like a try catch.
 
9:54 PM
@MooingDuck Because of an exception!
The same exception that caused your object to throw.
@MooingDuck No, it wouldn't.
 
@RMartinhoFernandes Good question.
 
@RMartinhoFernandes wait, are we talking about the same thing?
 
{
    foo a, b, c;
    throw blah();
    c.frob();
}
 
If b stops unwinding, c is already gone.
 
9:57 PM
@RMartinhoFernandes A scoped exception catcher would be problematic for the same reason.
 
Oh, I see what you mean. I was thinking that b's destructor would be "effectively" at the end of the block. so c would destruct. b would destruct and stop the unwind, and execution would continue at that place of the scope, which is between b's destructor and as. So the next step is as destructor would execute. This held togeather because I imagined the destructors as existing at that place in the code. But you are right that it doesn't quite work like that.
 
There's a (non-syntactic) reason a catch introduces a new scope.
This destructor thingies are very fine-tuned. If you try messing with them you need to be careful not to break it.
 

« first day (445 days earlier)      last day (4496 days later) »