MinekPo1 [She/Her]

nya !!! :3333 gay uwu

I’m in a bad place rn so if I’m getting into an argument please tell me to disconnect for a bit as I dont deal with shit like that well :3

  • 1 Post
  • 36 Comments
Joined 1 year ago
cake
Cake day: June 14th, 2023

help-circle
  • Agh I made a mistake in my code:

    if (recalc || numbers[i] != (hashstate[i] & 0xffffffff)) {
    	hashstate[i] = hasher.hash(((uint64_t)p << 32) | numbers[i]);
    }
    

    Since I decided to pack the hashes and previous number values into a single array and then forgot to actually properly format the values, the hash counts generated by my code were nonsense. Not sure why I did that honestly.

    Also, my data analysis was trash, since even with the correct data, which as you noted is in a lineal correlation with n!, my reasoning suggests that its growing faster than it is.

    Here is a plot of the incorrect ratios compared to the correct ones, which is the proper analysis and also clearly shows something is wrong.

    Desmos graph showing two data sets, one growing linearly labeled incorrect and one converging to e labeled #hashes

    Anyway, and this is totally unrelated to me losing an internet argument and not coping well with that, I optimized my solution a lot and turns out its actually faster to only preform the check you are doing once or twice and narrow it down from there. The checks I’m doing are for the last two elements and the midpoint (though I tried moving that about with seemingly no effect ???) with the end check going to a branch without a loop. I’m not exactly sure why, despite the hour or two I spent profiling, though my guess is that it has something to do with caching?

    Also FYI I compared performance with -O3 and after modifying your implementation to use sdbm and to actually use the previous hash instead of the previous value (plus misc changes, see patch).




  • honestly I was very suspicious that you could get away with only calling the hash function once per permutation , but I couldn’t think how to prove one way or another.

    so I implemented it, first in python for prototyping then in c++ for longer runs… well only half of it, ie iterating over permutations and computing the hash, but not doing anything with it. unfortunately my implementation is O(n²) anyway, unsure if there is a way to optimize it, whatever. code

    as of writing I have results for lists of n ∈ 1 … 13 (13 took 18 minutes, 12 took about 1 minute, cant be bothered to run it for longer) and the number of hashes does not follow n! as your reasoning suggests, but closer to n! ⋅ n.

    desmos graph showing three graphs, labeled #hashes, n factorial and n factorial times n

    link for the desmos page

    anyway with your proposed function it doesn’t seem to be possible to achieve O(n!²) complexity

    also dont be so negative about your own creation. you could write an entire paper about this problem imho and have a problem with your name on it. though I would rather not have to title a paper “complexity of the magic lobster party problem” so yeah


  • unless the problem space includes all possible functions f , function f must itself have a complexity of at least n to use every number from both lists , else we can ignore some elements of either of the lists , therby lowering the complexity below O(n!²)

    if the problem space does include all possible functions f , I feel like it will still be faster complexity wise to find what elements the function is dependant on than to assume it depends on every element , therefore either the problem cannot be solved in O(n!²) or it can be solved quicker








  • honesty I never understood why people consider malbolge so bad . sure its difficult AF to do anything in and the complexity gets quite higher still , but IMHO its just to abstract to be painful , it feels to different to feel like something you should be able to understand .

    honesty struggling to write simple operations in some of my own esolangs was way more mind-bendingly horrid than I think malbolge could be without making a compiler to it , while still feeling like I was programming .

    to be fair I also made ArrayFuck so yeah








  • no it still doesn’t because unless that ai will code in assembly (which you could argue is a statically typed programming language with just one type , but lets not be pedantic) , it will still use programming languages , which means it will still matter if a language something is made is statically or dynamically typed .

    even with the assumption that AI will be able to efficiency code in assembly , lets entertain the exponential growth version of ai often shown in fiction , it will still not be worth for that super intelligence to write in assembly (except for what we humans would call fun or for small cases where its necessary like os headers etc) because a compiler will do it faster and likely good enough , especially as it will then be able to make a better compiler . it will also likely not want to spend time/focus to scan the assembly code which is another advantage to not writing in pure assembly .

    making that statement requires a complete lack of understanding how programming works along with an over"optimistic" view on the future of ai nya