

Is it possible to get the rightmost NONZERO digit of a factorial without calculating for it?
Say 1000! = 2
Regards, Ian
*NO, this is not a homework.
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.





I assume you mean without calculating the factorial but some simpler, faster calculation? You can rewrite a factorial as a polynomial in n but I'm not sure if that gives you an easy pattern for the last digit. And by definition, all factorials except 1! and 0! are even. Does this have a practical application or are you just curious?
If you don't have the data, you're just another a**hole with an opinion.





Nope. This is part of the question set my adviser gave me to prepare for a certain competition.
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.





Ian Uy wrote: It is said that the most complex structures built by mankind are software systems.
I've heard that bandied about but I think I'll disagree. They usually quote Vista at 50 million lines of code yet the latest generation of processor chips boast over 2 billion transistors. And you could argue that much of what gets counted in an operating system are simply utilities that are applications running on the base system so the core is smaller still.
If you don't have the data, you're just another a**hole with an opinion.





Hi,
I tend to disagree. Hardware, especially CPU design, mainly consists of very repetitive structures, whereas software, all kinds of it, is very inhomogeneous. And a new CPU gets designed in a matter of months, a new OS takes several years.
That helps explaining why you would find less than 10 bugs in your CPU having 2 billion transistors, and several thousands of bugs in just 50 million lines of Windows code.
So if you want to compare complexity, I suggest you look at design effort, and number of bugs.





I still will disagree. In programming we keep using the same structures over and over again but insist on lovingly hand coding them each time. The chip makers have better tools and love to reuse their building blocks. A large part of their reuse is automated which explains the smaller number of bugs. They prove their components and then build up. Programmers make the same mistakes at ever increasing scales.
On another note, humans make machines with millions of parts. I will contend that one line of code is not equivalent to designing one mechanical part in complexity.
If you don't have the data, you're just another a**hole with an opinion.





Ian Uy wrote: Is it possible to get the rightmost NONZERO digit of a factorial without calculating for it?
Yes, for example the last nonzero digit of 1,000,000! is 4.
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."





Got it!... after about 10 mins of tinkering...
static int fac_last_digit(int x)
{
int res = x;
int mod = 10;
while (x > 1)
{
if ((res * (x  1)) % mod == 0) mod *= 10;
res = (res * (x)) % mod;
}
return (res / (mod / 10));
} The trick is to use the % operator with increasing powers of 10 depending on if the result is a multiple of the original modulus value...
(Needs tidying up a little)... why you need this is a mystery though.
Matthew Butler





Nice try, but you will quickly fall over without a large integer class. Even 1000! ends with 249 zeros, so mod will grow to about 10^249 or so.
If you get bored, try to write a routine to compute the last nonzero digit of googol! = (10^100)!, you should get 6.
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,
IMO this will behave much better; it gives 4 for 10000000, does not overflow, has no loops but uses a recursion (scaling down by a factor of 5).
private int rightmostNonzeroInFactorial(int n) {
int result = 1;
int count2 = (n+8) / 10;
int count3 = (n + 7) / 10;
int count4 = (n + 6) / 10;
int count5 = (n + 5) / 10;
int count6 = (n + 4) / 10;
int count7 = (n + 3) / 10;
int count8 = (n + 2) / 10;
int count9 = (n + 1) / 10;
int count10 = (n + 0) / 10;
count5 += count10;
if (count5 != 0) {
result = (result * rightmostNonzeroInFactorial(count5)) % 10;
count2 = count5;
}
count2 += 2 * count4;
count2 += 3 * count8;
count2 += 4 * count6;
count3 += 2 * count9;
count3 += 3 * count7;
int[] fact3 = new int[] { 1, 3, 9, 7 };
result = (result * fact3[count3 % fact3.Length]) % 10;
int[] fact2 = new int[] { 1, 2, 4, 8 };
int factor2=fact2[count2 % fact2.Length];
if (factor2 == 1 && count2 != 0) factor2 = 6;
result = (result * factor2) % 10;
return result;
}
Main principle is factors that are not multiples of 5 don't care about their digits except the lowest one (and also: there will be more powers of 2 than powers of 5).





Hi Luc,
I haven't worked through your code (are you sure the countN's do the right thing?).
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!
Using this the problems reduce easily.
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,
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<p?jxsgb$f4ia>  128 bit encrypted signature, crack if you can </p?jxsgb$f4ia>






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<p?jxsgb$f4ia>  128 bit encrypted signature, crack if you can </p?jxsgb$f4ia>





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 !



