I want to create a command that, for a given integer n
, type sets a simplified square root of n
. For example, the output of
\rsqrt{4}
\rsqrt{8}
\rsqrt{18}
\rsqrt{7}
would be the same as that of
2
2\sqrt{2}
3\sqrt{2}
\sqrt{7}
where \rsqrt{}
is the command in question.
I know that the algorithm would look somewhat like this
i = square root of n rounded down
while i > 0:
if n is divisible by i²:
simplification is i\sqrt{n/i²}
break loop
i = i - 1
%the simpification will always be found
%since every n is divisible by 1
where n
is the given integer, i
is the number before \sqrt
and n/i²
is the argument of \sqrt{...}
.
But I have no idea how to implement this in latex?
EDIT: Clarified that the input number will always be an integer.
Best Answer
The algorithm in the question is very inefficient: except of course if the original integer is a perfect square.
This answer (in chronological order):
an approach with macros which mimics the simplest factorization algorithm,
an expandable approach using the algorithm as in OP. update very embarrassingly, the author had not understood the OP's algorithm and after having found a simplifying
I
such asI^2
dividedN
, he went one recursively withN<-N/I^2
not understanding that the algorithm could stop there. (as a pale excuse, he had implemented first the "bottom-up" way, which needs recursivity, contrarily to the "top-down" (less efficient) way). The answer is thus updated, apologies to all generous trustful early up-voters.I am updating again (sorry) because I have now read more of
xintexpr.sty
's documentation, and I switched for efficiency fromi=sqrt(N)..1
toi=-sqrt(N)++
(there is no--
available, hence a trick with minus sign). The former generates beforehand the whole list offloor(\sqrt{N})
numbers (sqrt
means truncated square root in\xintiiexpr
), the latter is an iterator which doesn't generate things beforehand. Furthermore the former syntax can only generate about5000
values (sqrt(N)..[-1]..1
would have no such limitation, but still would generate everything beforehand).an expandable implementation of faster (high-school factorization type) algorithm as in approach 1.
To be honest 2., 3. and even 1. would probably be better written entirely using
\numexpr
as their pretence at handling numbers bigger than2^31
is a bit far-stretched, it takes time with a prime number of 10 digits to do tens of thousands of divisions to conclude it was square-free ... Implementation 2. has an intrinsic limit to2^62
because the square root must be a TeX number (due to some construct inside).In 2. and 3., we push a bit beyond reasonable range the possibilities of
\xintexpr
syntax with recursive sequences. The notation is a bit cumbersome. Besidesxintexpr.sty 1.2g
is needed because it changed relevant syntax.First approach (we change the algorithm)
Not to say that this is an easy problem. A bit of googling reveals that apparently mathematicians currently believe that finding the square free radical of an integer may be as hard as complete factorization: https://math.stackexchange.com/questions/171568/finding-the-radical-of-an-integer and https://math.stackexchange.com/questions/14667/square-free-integers-factorization.
Here is an approach (using macros) which mimicks simplest form of factorization algorithm.
Package
xintexpr
is used only in order to allow inputs such as1e7
or even expressions. It also loadsxinttools
which is used in the syntax.Apart from that all operations are done with macros available from
xint
. As we deal in the example almost only with numbers<2^31
we could employ a variant where all operations would be done using uniquely\numexpr
, naturally that would be quite faster.The code uses
\xintiiDivision
which computes simultaneously quotient and remainder. This is why\xintAssign
is used to store them into two macros\A
and\B
. The code examines if\B
vanishes to detect the divisibility by aQ=P^2
.Second approach (same algorithm as in OP, expandable implementation)
With the original algorithm. Here we define
\ExtractRadical
which expandably returnsA,B
withN=A^2 B
. A non-expandable wrapper re-cycles\Rsqrt
from faster approach above to produceA\sqrt{B}
, distinguishing cases of negativeN
orN=0, 1
.I have added code comments to explain implementation. An earlier version was very lame (see top of answer) and additionally required
xintexpr 1.2g
which is not the case anymore.Third approach: again the faster algorithm, but expandably.
It would be more reasonable to code this à la
\numexpr
but well. Details in the code comment. The example has now 51 random examples, and funny enough the missing one (from first approach) turned out to be a random square (with the random seed to pdftex random number generator set at123456789
).Update (2017).
Here is no-package expandable macro, if needed. It expands to
I,J
where originalN
isI**2 times J
andJ
is square-free. Uses only\numexpr
. Limited to<2**31
integers. Works from low to big, same as elementary factorization method. Stopping criteria should be improved, the comment below applies here too.