

Hi Peter,
1.
countN tells me how many factors of n! end on digit N
2.
the recursion takes care of your q!
3.
I ran a check for all [1,500] and for 10000000
regards,





Luc Pattyn wrote: countN tells me how many factors of n! end on digit N
OK now I see what you are doing. I'm sure you have some very clever reason for this, but it is not clear to me why you do
count5 += count10;
if (count5 != 0)
{
result = (result * rightmostNonzeroInFactorial(count5)) % 10;
count2 = count5;
}
and not what I would expect:
if (count5 != 0)
{
result = (result * rightmostNonzeroInFactorial(count5)) % 10;
count2 = count5;
}
if (count10 != 0)
{
result = (result * rightmostNonzeroInFactorial(count10)) % 10;
}
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





Hi Peter,
the way you propose the factors that end on 5 don't get represented by count5 factorial
(they only need odd multiples of 5), hence the recursion would not be correct.
I expect the theory that explains my code would be the same as the one that led to the
formula you've mentioned before.





Ah now I see (it's late here
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





cp9876 wrote: ...There is a little known fact (don't ask me how I know it!) that
if n = 5q+r with 0 <= r < 5
then n! has the same rightmost nonzero digit as 2^n x q! x r!
That should be 2^q rather than 2^n, and then it's valid for all n > 4. Removing recursion, here's one way to write it (in Python):
def f(n):
result = 1
while n > 1:
n, r = divmod(n, 5)
result = result * (6, 2, 4, 8)[n & 3] * (1, 1, 2, 6, 4)[r] % 10
return result
and that can be simplified a bit by using a larger table:
FACTAB = 6, 6, 2, 6, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 8, 8, 6, 8, 2
def f(n):
result = 1
while n > 1:
result = result * FACTAB[n % 20] % 10
n return result





I believe this to be an ACM question from either 96' or 97'
bool nonzerodigit(const unsigned int& n, unsigned int& result)
{
if (n > 100000) return false;
unsigned int result = 1;
for (unsigned int i = 1; i <= n; ++i)
{
unsigned int f = i;
while (0 == (f % 5))
{
f /= 5;
result /= 2;
}
result = (result % 100000) * f;
}
result %= 10;
return true;
}
100000 is an upper sanity bound and also a quantizer for the minimum required 6 "least significant" digits.





Thank you!
I am training for the next ACM ICPC Regionals.
It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.





Hello,
I'm putting together a Silverlight 2 demo application. It is going to be a simple 2D tank game where you can use the arrow keys to rotate and move the tank. The tank can point in any direction (360 possible directions, right?). I've written the code to rotate the tank, but I'm not sure where to begin regarding moving the tank. How can I take the angle of the tank (say, 156 degrees for example) and use that to determine the next x,y position of the tank when it moves forward?
I'm sure there must be a simple equation for this, but I don't know what it would be called or even how to google this problem.
Any ideas?
Thanks,
Ian





Define the motion using a vector. The position coordinates are given by:
x = r*cos(theta)
y = r*sin(theta)
where r is the distance traveled and theta is the angle. You can get more description here[^]. You'll also have to assign a velocity.
I'm the ocean. I'm a giant undertow.





Beat me to it.
(Within 3 minutes, more than 3 hours from the original question, what are the chances of that?)
Matthew Butler





Pretty low I would imagine....wacky!
I'm the ocean. I'm a giant undertow.






Just use basic geometry/maths...
nextXpos = lastXpos + speed * sin(angle);
nextYpos = lastYpos  speed * cos(angle);
[angle is measured from the vertical, clockwise]
The only things you need to remember are:
> Math.Sin and Math.Cos take the angle argument in radians not degrees.
> Sin and Cos return double precision numbers: which may round to 0 or 1 if you are using integer positions and therefore the tank will not move as you want.
Hope this helps.
Matthew Butler






Edmundisme wrote: Thanks!
Well, should be tanks, instead...
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
 Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
 Iain Clarke





Hello,
i have set of 2D points and i want to offset with a given distance (like offset command in AutoCAD)
i do not know how to deal with corners. i have searched on Internet, there are advanced methods like straight skeletons etc. but my polyline is not self crossing and no holes in it.
Is there any simple method? any references?
Best Regards.
Bekir





Why can't you just iterate through the points and add your offset to each one? It seems like this should translate the corners along with everything else.






beko wrote: Just translating the edges with the offset distance will not work.
Why not?
beko wrote: I have found an algorithm not tested throughly, but it is working at least for my very simple 3 points polyline test
What kind of test you did?
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
 Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
 Iain Clarke





Hello,
At the end, it is a translation however it must be implemented with respect to the normals, as far as i read through if it is a parametric curve then it is rather complicated. If you like to see how much it can further get complicated, you can have a look at the link below.
http://timeguy.com/cradekfiles/emc/liu2007_line_arc_offset.pdf[^]
for the test, i have just created a polyline with three points and used the algorithm from Eduardo in my earlier reply, and compared it with AutoCAD output
Best Regards.





That paper seems to give a good description of how to do it. It's complicated, you will have lots of cases  you'll just have to get used to it.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





There is no simple solution to this problem, the best known general solution, is to create capsules between consecutive point pairs of your polyline where the capsule width is the offset, then union the capsule outlines. The capsule may be centered around the edge or it may be biased towards one side of the edge it is really up to the end requirement. For the union operation use something like Alan Murta's Generic Polygon Clipper library.
If you know your polyline is enclosed and represents a convex polygon, then simply calculate the centroid, then offset each edge by the product of the desired offset amount and the vector composed of the midpoint of the edge at hand minus the centroid.
A simple example can be found here:
http://www.codeproject.com/KB/recipes/Wykobi.aspx





Thank you for the all answers,
I will have a look at it.
Best Regards.





For 0 < a, b < 1, if it makes a difference.
Thanks!





It is only periodic is a/b is rational and then it is fairly easy to work out.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





If you consider the wave form:
y(t) = A*sin(w*t + q)
A is the amplitude of the wave (height up the y axis)
q is the phase shift of the wave (left/right shift along the x axis)
t is a variable
w is the angular frequency
Angular frequency equals to 2*PI*f > where f is the frequency of the wave.
The period of the wave (t) is 1/f. (t = 1/f)
A Cosine wave is just a Sine wave with a 90 degree phase shift.
Cheers,





Since cos(ax) sin(bx) = 1/2 sin((a+b)x) + 1/2 cos((ab)x) should be (a+b)/(ab) rationale.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
 Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
 Iain Clarke





im trying to convert Quaternion to Euler but i dont have appropriate code, i searched on lots of sites but their converting code do not match with converting back, mean, if i convert from Quaternion to Euler then i convert back the result value to Quaternion, i got different output, here is my code
public static float[] ToEuler(double tmp_x, double tmp_y, double tmp_z,double tmp_w)
{
float[] Euler = new float[3];
double sqr_X = tmp_x * tmp_x;
double sqr_Y = tmp_y * tmp_y;
double sqr_Z = tmp_z * tmp_z;
double sqr_W = tmp_w * tmp_w;
const double radian = 180 / Math.PI;
double check = tmp_x * tmp_y + tmp_z * tmp_w;
double unit = sqr_X + sqr_Y + sqr_Z + sqr_W;
if (check > 0.499 * unit)
{
Euler[0] = 0;
Euler[1] = (float)(radian * Math.Atan2(tmp_x, tmp_w));
Euler[2] = (float)90;
return Euler;
}
else if (check < 0.499 * unit)
{
Euler[0] = 0;
Euler[1] = (float)(radian * Math.Atan2(tmp_x, tmp_w));
Euler[2] = (float)90;
return Euler;
}
Euler[0] = (float)(radian * (Math.Atan2(2 * (tmp_x * tmp_w + tmp_y * tmp_z), (sqr_X  sqr_Y + sqr_Z + sqr_W))));
Euler[1] = (float)(radian * (Math.Asin(2 * (tmp_x * tmp_z  tmp_y * tmp_w))));
Euler[2] = (float)(radian * (Math.Atan2(2.0 * (tmp_x * tmp_y + tmp_z * tmp_w), (sqr_X  sqr_Y  sqr_Z + sqr_W))));
return Euler;
}
public static float[] ToEulerA(double x, double y, double z, double w)
{
double sqw = w * w;
double sqx = x * x;
double sqy = y * y;
double sqz = z * z;
double unit = sqx + sqy + sqz + sqw;
double test = x * y + z * w;
double RX = 0;
double RY = 0;
double RZ = 0;
if (test > 0.499 * unit)
{
RX = 2 * Math.Atan2(x, w);
RY = Math.PI / 2;
RZ = 0;
}
else if (test < 0.499 * unit)
{
RX = 2 * Math.Atan2(x, w);
RY = Math.PI / 2;
RZ = 0;
}
else
{
RX = Math.Atan2(2 * y * w  2 * x * z, sqx  sqy  sqz + sqw);
RY = Math.Asin(2 * test / unit);
RZ = Math.Atan2(2 * x * w  2 * y * z, sqx + sqy  sqz + sqw);
}
RX = 180 / Math.PI * RX;
RY = 180 / Math.PI * RY;
RZ = 180 / Math.PI * RZ;
return new float[] { (float)RX, (float)RY, (float)RZ };
}
im not sure which one is correct or both are incorrect...
any idea to solve this ?
thanks
TVMU^P[[IGIOQHG^JSH`A#@`RFJ\c^JPL>;"[,*/+&WLEZGc`AFXc!L
%^]*IRXD#@GKCQ`R\^SF_WcHbORY87??6?N8?BcRAV\Z^&SU~%CSWQ@#2
W_AD`EPABIKRDFVS)EVLQK)JKSQXUFYK[M`UKs*$GwU#(QDXBER@CBN%
Rs0~53%eYrd8mt^7Z6]iTF+(EWfJ9zaKi?TV.C\y

128 bit encrypted signature, crack if you can






unfortunately i got code from that site, that site converter have some incorrect conversion, eg. at the end of page you will find a java converter, write real = 1, i = 1, and output will be 116.56505117707799, now put this 116.56505117707799 in Euler to Quaternion converter on another page and now result is completely different, why ?
TVMU^P[[IGIOQHG^JSH`A#@`RFJ\c^JPL>;"[,*/+&WLEZGc`AFXc!L
%^]*IRXD#@GKCQ`R\^SF_WcHbORY87??6?N8?BcRAV\Z^&SU~%CSWQ@#2
W_AD`EPABIKRDFVS)EVLQK)JKSQXUFYK[M`UKs*$GwU#(QDXBER@CBN%
Rs0~53%eYrd8mt^7Z6]iTF+(EWfJ9zaKi?TV.C\y

128 bit encrypted signature, crack if you can





You could just reference Microsoft.DirectX





Hi,
Can anyone point me to algorithms for drawing a line/spiral/ellipse, if its a c++ code then its my lucky day otherwise anything will do.
Also i need to draw a gradient as well and i cant use GradientFill api (lucky me )
Any help at all will be much appreciated
Thanks
C++ where friends have access to your private members !





Monty2 wrote: Can anyone point me to algorithms for drawing a line/spiral/ellipse, if its a c++ code then its my lucky day otherwise anything will do.
Is something like this[^] sufficient? It's pretty nice  I've used it in one of my projects.
Less in your favour is this[^] implementation in C#.





Well i am sorry if i was not clear on the question i actually need to implement functions like
DrawLine(POINT ptFrom,POINT ptTo);
DrawGradient(CRect rc,COLORREF FromColor,COLORREF ToColor);
For some reasons i cant use the stock functions provided (i need to get all the points in the line)
C++ where friends have access to your private members !






Monty2 wrote: For some reasons i cant use the stock functions provided
Care to give us a clue to why so we know better what to suggest?
If you don't have the data, you're just another a**hole with an opinion.





Tim Craig wrote: Care to give us a clue to why so we know better what to suggest?
Fair enough, let me explain it further
I need to draw N rectangles side by side (their centers lying on a line or trajectory).
Works like this, user gives two points (left and right) then i need to draw a series of rectangles from the first point to the second with the rectangles centers lying on the line.
i figured for that i need to calculate the points that will lie on that line, hence the requirement for an algorithm that will give me the points that will lie on a line(x1,y1,x2,y2)
Secondly user will provide the color of the first rectangle and the last and i need to fill the rest of the rects with the gradient color, hence the requirement for a gradient algorithm
Here is a sample image (it uses sine wave i think instead of a line)
Sample[^]
And lastly thanks for your valuable time
C++ where friends have access to your private members !





Well, this might be a place to get started. Bresenham's algorithm[^] certainly picks pixels to draw straight lines and some other curves. You might also check some of the 3D drawing class libraries, like VRML or the library that originated at SGI, as they often implement a process they call "extrude" where they sweep a shape through space that follows a curve, a cylinder is an example of extruding a circle along a straight line. I don't think they use pixels generally but you might get some ideas.
If you don't have the data, you're just another a**hole with an opinion.





Thanks a bunch for your ideas the Bresenham should work perfectly i think
C++ where friends have access to your private members !





For example, used for video conference or video capture.





followait wrote: For example, used for video conference or video capture.
Oh, probably some DCT (discrete cosine transform) derivative like H.261. It's an ITU standard suited for twoway communication over ISDN. It supports fairly high data rates as well (i.e. multiples of 64Kbit/sec).





Currently h264. All HDs are in H264 for example.
Back then it was xvid.





Hi,
All of you must have herd of Best fit also, but i would give a brief , just in case.
Say i have slots of 50 KB, and there are some codes of different sizes say [10KB,11KB,23KB,34KB,2KB,28KB,31KB,9KB]
Now i have to fit all the elements in the different 50KB Slots such that i make the optimum use of the space. Like:
31+9+10 = 50KB  1st slot.
11+34 = 45KB  2nd slot...
I need an algo for the same in C#..
Thanks in advance...





The best fit is a rather lengthy algorithm to implement. I would try sorting in descending order before trying to assign bins. Then you'll have to loop through all the bins and assign as appropriate. You also have the possibility of increasing the numbers of bins. Assign elements to the bin that is most full that can accomodate your element. At this point you can increase the number of bins if you like. Continue in this manner....





This is a standard Multiple Knapsack[^] problem, there are lots of references on the web and a variety of solution trchniques with different ranges of applicability. One general code (fortran though, not c#) is TOMS ALgortihm 632[^]
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."





You are probably going to have to live with an imperfect solution. This looks a lot like subsetsum, which iirc is an NP hard problem





Hello,
Best Fit problem as applies to computer science involves variable size storage blocks as well as variable size data to be put into the storage blocks notably without combining data chunks before storage (see Knuth, Vol. I).
What you have described is the timeworn knapsack problem, aka circus train problem. Simply stated: What is the packaging arrangement of a fixed set of variably sized objects into uniform size containers that fills the fewest containers?
Problem size will be a considerable obstacle here. Consider unfavorable size distributions in your set of variables that yield many size combinations to be generated, tested, and compared with the previousbest combination. And how many possible combinations of these combinations are possible?
Anyway, I think you should postulate some modest inputs and do some pencil scratch before hunting down code or algorithm.
Tadeusz Westawic
An ounce of Clever is worth a pound of Experience.





I want to implement an algorithm in which I need to put some nodes(points)in an environment and segments which connect theses nodes in some way to each other. The environment is occupied with some obstacles(simple shapes or polygons)! How can I determine when collision exists between nodes or segments and the environment's obstacles! Thanks so much in advance.





It depends on the accuracy that you want. For relatively inaccurate detection you can use the bounding box of your shapes.
There are some nice bounding box based algorithms in OpenGL that you can use: here[^].
There's also a nice CP article here[^].
EDIT: It helps to explain why you gave me a '1vote'...
modified on Tuesday, June 10, 2008 3:30 AM





The solution requires the use of a spatial container. You place all your environment objects into the container, then as you process your dynamic objects you query them against the spatial container. The result should provide back the intersecting objects. Depending on the dimensionality of the objects you could either use a quadtree or an octree.




