How to deal with broken collision detection on a deterministic physics engine?

I've made a very simple and primitive JavaScript canvas engine that is simply not dependent on time, as in it assumes that t = 1 in the formula v = u + at - v is the current velocity, u the initial velocity and a is acceleration due to gravity.

Now, the issue with this method is that if the value of gravity, or velocity is large enough that the object it should collide, it just goes right through it. Now, I have been told that if time was a parameter, we could just increase the frame rate and dilate the time to resolve this, but this would mean that the engine would no longer be deterministic - as in, the simulation would not work out the exact as it we assumed it to be, owing to hardware and software requirement like decimal point handling and precision.

How can we deal with this issue on this simple deterministic engine, and improve collision detection?