Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[j.h]

If the goal was to minimize sum of the vector components, not its length, it would be an example case of linear programming problem which is not that hard to solve and there are freely available solvers.
But as it stands, it is a case of quadratic programming, which is more complex. After a quick look at the wiki, it seems your case is solvable by the ellipsoid method in polynomial time, but the best thing to do would be to look for some existing quadratic programming solver.

[MagmaMcFry]

If the goal was to minimize sum of the vector components, not its length, it would be an example case of linear programming problem which is not that hard to solve and there are freely available solvers.
But as it stands, it is a case of quadratic programming, which is more complex. After a quick look at the wiki, it seems your case is solvable by the ellipsoid method in polynomial time, but the best thing to do would be to look for some existing quadratic programming solver.

Yeah, I saw the wiki page too, but I was specifically looking for some algorithm that performs really well with this particular kind of subproblem. But I didn't find more specific algorithms, so I made my own. Runs in O(k(k+n)), worst case. Suck it, quadratic programming.

[Bauglir]

This is kind of a theory question, and might even belong in the math thread. I'm trying to work something out for Dungeons and Dragons shenanigans, so obeying physical laws isn't strictly necessary (we're allowed to have stuff happen instantaneously, for instance, rather than having a minimum length of time).

If you have a recursive operation with no base case, instantaneous (or, in other words, length 0 time) execution of each iteration of that operation, and a finite amount of time over which it is executed (6 seconds in this case, but it should be unnecessary to specify), how many iterations execute by the end of that time?

In other words, let's say I have the following bit of pseudocode, and a processor that can perform one operation every 0 seconds:

X{
Cast Greater Celerity;
X;
}

How many castings of Greater Celerity come out of that after 6 seconds of execution. Intuition tells me infinity - I don't know if that's reasonable (maybe it's just "an arbitrarily large, but not infinite, number"), and I also don't know how infinite it is (intuition suggests that it'd be aleph(0), but intuition is well known for being awful at answering these kinds of question). I also spy a potential divide by 0 in there, which I don't really know how to deal with.

[MadocComadrin]

It depends what you really mean by instantaneous. If you mean exactly 0 time, then yes, it's infinity, assuming other things don't get in the way. If it's an infinitesimal amount of time, then there might be a solution via calculus.

[Nadaka]

depending on edition... you can only cast one instantaneous spell per round.

[Skyrunner]

I don't know, but wouldn't it be either optimized out, or how many ticks the processor does in a that time? I didn't quite understand the question. Doesn't Cast Greater Celerity mean it has a non-zero iteration time? @_@
X{X} would probably be the number of ticks the processor works at >_< Not so sure about the one in the question.

[Bauglir]

Well, to go into more specifics, you get something like this. We're working with traps, here - you trigger the first one with whatever you want (say, pulling a lever). This triggers (by, say, casting mage hand on a lever) the second trap, which triggers two traps - a magic "trap" that casts Greater Celerity on somebody in a particular square (you need some shenanigans to make the spell non-personal so that it can actually be made into a trap, I think, but once that's taken care of you're good to go), and a trap that triggers the second trap again.

Traps are allowed to reset "immediately", whatever that means, and D&D doesn't specify a minimum amount of time that has to pass between things occurring - there's none of the quantum physics that sets a hard cap on how fast things can occur*, nor do you have to obey any of the laws of thermodynamics. Characters have a set number of actions that normally handles that sort of nonsense, but to the best of my knowledge, traps don't actually use actions. However, I can't honestly tell you what all that means in terms of how many times you can make something happen in a round, because I lack both a real math background and a computer science background, so I... really don't know how to handle the question in a way that isn't basically guessing.

I posted it here mostly because, based on the diagram and that I'm constructing this as what boils down to a "While" loop with no condition for termination, it seems like it comes down to very similar logic to attempting to execute an infinite loop in a program.

I recognize that this is stupid, but the goal here is to reach level infinity so that's kind of a given.

*I also don't have the physics background necessary to know if this is a sentence that makes sense, or one that is as close to making physical sense while being intelligible to a layperson.

[Skyrunner]

Well, if you do it on a computer, the maximum possible speed is the number of ticks on your processor per second, as far as I know. >_<
Or, if the Cast Greater_Celerity function has a significant runtime, however times that works.

[MagmaMcFry]

I'd assume your universe will crash because stack overflow.

[Elu]

Well, to go into more specifics, you get something like this. We're working with traps, here - you trigger the first one with whatever you want (say, pulling a lever). This triggers (by, say, casting mage hand on a lever) the second trap, which triggers two traps - a magic "trap" that casts Greater Celerity on somebody in a particular square (you need some shenanigans to make the spell non-personal so that it can actually be made into a trap, I think, but once that's taken care of you're good to go), and a trap that triggers the second trap again.

Traps are allowed to reset "immediately", whatever that means, and D&D doesn't specify a minimum amount of time that has to pass between things occurring - there's none of the quantum physics that sets a hard cap on how fast things can occur*, nor do you have to obey any of the laws of thermodynamics. Characters have a set number of actions that normally handles that sort of nonsense, but to the best of my knowledge, traps don't actually use actions. However, I can't honestly tell you what all that means in terms of how many times you can make something happen in a round, because I lack both a real math background and a computer science background, so I... really don't know how to handle the question in a way that isn't basically guessing.

I posted it here mostly because, based on the diagram and that I'm constructing this as what boils down to a "While" loop with no condition for termination, it seems like it comes down to very similar logic to attempting to execute an infinite loop in a program.

I recognize that this is stupid, but the goal here is to reach level infinity so that's kind of a given.

*I also don't have the physics background necessary to know if this is a sentence that makes sense, or one that is as close to making physical sense while being intelligible to a layperson.

The problem as i see it is:
You need to define a "quantum" of time(aka the smaller amout of time that pass between a certain valid state of the universe and the next), and base your durations on that, premising that can't exist any event with duration 0.
Let's say we use mall's sliding doors as the "trap" and minutes as the "quantum". Since the doors open(sprung) and closes(reset) in a matter of seconds, we will have a resetting time of the doors of 0 quantum of time, which mean that we can't tell if the trap has sprung(because we will always see the doors closed), or more precisely we can't tell when and if the trap changes state from to armed to activated and back.
In recursion term this means that you have a recursion clausole without a termination one, and you saw it right, it will loop inifinitely(theoretically) and crash your program(pratically) as magmaMcFry already said.

How to avoid this? scratching the "istantaneous" thing. To normal human a photo flash is istantaneous, but truly it isn't. Just use a "time unit" and a "micro time unit", with 1TU=100MTU and set the magic and other "istantaneous" effect to use 1 MTU, and the other things to behave with the TU as the quantum of time...

[Nadaka]

By D&D 3 to 3.5 edition and rules, traps that cast spells do indeed have a cast time of instantaneous and you (the trap) can only cast one such spell per round.

[Thief^]

I would say that the trap resets immediately, but not instantaneously, so it couldn't be triggered again within the one round. You could make it trigger once per round automatically though.

[Bauglir]

By D&D 3 to 3.5 edition and rules, traps that cast spells do indeed have a cast time of instantaneous and you (the trap) can only cast one such spell per round.

Hm, where's that second part? That'd require the trap to be using actions, which would be good to know but I couldn't find any references to. Definitely does wreck the idea, though.

[Nadaka]

By D&D 3 to 3.5 edition and rules, traps that cast spells do indeed have a cast time of instantaneous and you (the trap) can only cast one such spell per round.

Hm, where's that second part? That'd require the trap to be using actions, which would be good to know but I couldn't find any references to. Definitely does wreck the idea, though.

I believe it was in one of online articles on the wizards web site where it was clarified. It won't be easy to find a reference, I have not been there much at all since they screwed everything up with 4e/gleemax.

[Bauglir]

By D&D 3 to 3.5 edition and rules, traps that cast spells do indeed have a cast time of instantaneous and you (the trap) can only cast one such spell per round.

Hm, where's that second part? That'd require the trap to be using actions, which would be good to know but I couldn't find any references to. Definitely does wreck the idea, though.

I believe it was in one of online articles on the wizards web site where it was clarified. It won't be easy to find a reference, I have not been there much at all since they screwed everything up with 4e/gleemax.

That's pretty fair, I ditched them around then, too. Anyway, I'll call it quashed for now.