Change behaviour of MOD and DIV operators
Closed, ResolvedPublic

Description

Author: omniplex

Description:
MOD and DIV behave different than in any programming language I've heard of.

1: Apparently "x MOD y" is handled like "trunc(x) - trunc(y) * trunc(x / y)",

e.g. "8.9 mod 3 = 2", "8 mod 3.2 = 2", "8 mod 2.7 = 0".

2: "x DIV y" is a misleading synonym for "x / y", no integer division.
3: A desperately needed "trunc" is missing, see [[m:Template talk:YMD2MJD]].

Proposed "fix" (or rather feature request):

2': Let "x DIV y" return "trunc( x / y )" also known as integer division.
3': This improved DIV automagically offers "x DIV 1" to get "trunc( x )".
1': Let "x MOD y" return "x - y * (x DIV y)" using the improved DIV.

With these two fixes (not counting 2') porting algorithms like Euclid's
GCD or date + time calculations should be more straight forward.

Using two #ifexpr: plus two #expr: +/-"0.5 round 0" to emulate trunc is
a royal PITA for formulae needing dozens of signed integer divisions.

The equation x MOD y = x - y * (x DIV y) should be okay, otherwise kill
DIV, as is it's at best redundant (but more likely harmful).


Version: unspecified
Severity: trivial
URL: http://meta.wikimedia.org/wiki/Help:Calculation

bzimport added a subscriber: Unknown Object (MLST).
bzimport set Reference to bz6068.
bzimport created this task.Via LegacyMay 24 2006, 2:49 AM
bzimport added a comment.Via ConduitMay 24 2006, 9:04 AM

robchur wrote:

Last time I checked, http://meta.wikimedia.org/wiki/Talk:ParserFunctions was the
place where discussion on this extension was taking place.

bzimport added a comment.Via ConduitJun 16 2006, 11:02 PM

ezyang wrote:

Implements trunc operator, and some stylistic changes

Whee, trunc operator added. I didn't address any of the other bug problems.

attachment Trunc.patch ignored as obsolete

bzimport added a comment.Via ConduitJun 16 2006, 11:12 PM

ezyang wrote:

Fixes bug completely

This patch fixes the bug completely but changes existing behavior (which could
cause trouble for people).

attachment FullPatch.patch ignored as obsolete

bzimport added a comment.Via ConduitJun 16 2006, 11:16 PM

ezyang wrote:

All that needs to happen now is patch review and then commit into SVN. Tim
Starling, I'd like to comment: "What a fantastic piece of code!" Even without
any documentation whatsoever, I was able to figure out exactly what to do to
extend it. Kudos to you.

As I commented previously, the second patch may be troublesome because it
changes behavior. However, Omniplex and Patrick seem to be the only people
(correct me if I'm wrong) who really use these functions to their full extent,
so I think we can trust them to go on a wild goose chase to fix the functions.

However, as I've been arguing at [[m:Talk:Date and time computing]] and as I'll
argue here, there's is absolutely NO REASON why we should be implementing
algorithms in wikitext. Please do it in PHP. Really. For performance and
readability reasons.

bzimport added a comment.Via ConduitJun 17 2006, 6:02 AM

omniplex wrote:

Other folks doing interesting stuff with templates:
[[User:Algorithm]], [[User:AzaToth]], [[User:CBDunkerson]],
[[User:Ed_Poor]], [[User:Gangleri]], [[User:Ligulem]],
[[User:Pathoschild]], [[User:Verdy_P]], [[User:Xaosflux]],
and Locke Cole. Incomplete list, JFTR.

Adapting templates to an improved MOD should be simple,
but getting rid of the then unnecessary ROUND hacks will
take some time (some of these hacks introduced hard to
conditions like "works for day numbers > -700000000001").

bzimport added a comment.Via ConduitJun 17 2006, 3:56 PM

ezyang wrote:

Which is, in all likelihood, exactly why the behavior change should get added in
as soon as possible.

Verdy_p added a comment.Via ConduitNov 8 2006, 8:35 PM

For modular (cyclic) arithmetic, it would be much simpler if we had the
following operators:

  • "x '''trunc''' n" : quite similar to "(x + 0.5) round n", but always truncates

down (including for negative numbers!) to n decimals ; this avoids testing the
sign; with it we can compute:

  • "x '''trunc''' 0" equals "floor(x)"
  • "(x+0.5) trunc 0" is the TRUE rounding of x (working also for numbers near

zero and negative numbers, and rounding of numbers exactly halfway between two
integers will alwyas be upward, including for negative numbers)

  • "x '''cdiv''' y" : cyclic integer division, result is: "(x/y) trunc 0", i.e.

mathematically: floor(x/y)

  • "x '''cmod''' y" : cyclic modulo, result is: "x - (x cdiv y)*y", i.e.

mathematically: x - floor(x/y)*y
Date, calendar and astronomical computing would be much simpler with them and
more accurate.

Verdy_p added a comment.Via ConduitNov 8 2006, 8:58 PM

Note that I propose the names "cdiv" and "cmod" only to avoid breaking formulas
already using div and mod. The ''c'' stands for "cyclic".

Also the proposed "trunc" keeps the same binary syntax as "round", but is
specifically designed towards mathematical calculation; that's why it uses a
consistant truncation towards minus infinite and not towards zero (which would
break cyclic arithmetic).

"x trunc n" can be computed mathematically as: "floor(x * pow(10, n)) / pow(10, n)"
For efficiency, we don't necessarily need n to be any real number, and
implementation where n is first converted to an integer wuold be fine. But in
PHP programming, we don't need to test that (as this would requiring adding more
code just to initialize a table of constants for powers of 10 and to check the
integer range for the value of n, even if it is first converted to an int. So
let's just just the math function "pow(x, y)" which is built in PHP's math module.
Note that this builtin pow() function is already accurate for pow(10, 0) and
already returns 1 exactly, so this won't affect the precision of common
expressions like:

"x trunc 0"

which will be computed as floor(x*pow(10,0))/pow(10,n) == floor(x*1)/1 == floor(x)

Note also that the value of n may be negative:

x trunc -2

means floor(x/100)*100 i.e. it truncates to the immedialy lower exact hundreds. And

(x+50) trunc -2

means rounding to the nearest exact multiple of 100 (including for negative
numbers).

With the trunc operator made available in #expr in MediaWiki, we can also
compute ceil(x) very simply as:

-(-(x)trunc 0)

because ceil(x) == -floor(-x)

Verdy_p added a comment.Via ConduitNov 8 2006, 9:23 PM

Note finally that the proposed cdiv and cmod will respect the expected equation:
x cmod y == x - (x cdiv y)*y
which is CRITICAL for any computing based on modular arithmetic and for
astronomical and physical cycles (whose length or period, i.e. the y value, are
NOT necesarily integers).

Another rounding mode used in financial applications is rounding towards
infinite of the same sign (it is used notably for the conversion between
currencies). This mode is near from what "round" currently computes in Wiki;
this is based on the conversion of floats to integers with a (int) or (long)
typecast, but this typecast is not completely safe due to the limited value
range supported by "int" and "long" datatypes. So "round" is bogous for such
applications.

That's where it is possible to implement a financial rounding operator:
"x fround n", computable like this in PHP:
(x < 0) ? ceil(x*pow(10,n)-0.5)/pow(10,n) : floor(x*pow(10,n)+0.5)/pow(10,n)

Verdy_p added a comment.Via ConduitNov 8 2006, 9:36 PM

Note that the proposed "fround" is definitely not usable for cyclic computing
without using tests for the sign (or for the range of the value if x is offseted
positively to compensate the impact on negative numbers.

"fround" above looks like a better (safer) version of "round" but will be
different because it does not depend on the way typecasts to ints are
implemented in the current port of PHP (this depends on the underlying
architecture!)

Replacing the current implementation of "round" by the one used in "fround"
above would not affect the compatibility in almost all cases (including for date
computing which are currently written using Wiki's "round"). The difference
appears only for very large integers (and explains why date computing still does
not work with very far years in the future or in the past, but the difference is
not within the scale of human written history, so this is not dramatic...).

AzaToth added a comment.Via ConduitNov 12 2006, 5:29 PM

Comment on attachment 1973
Fixes bug completely

This patch is broken against current SVN

AzaToth added a comment.Via ConduitNov 12 2006, 6:38 PM

a probable implementation of function needed to resolve the problem

Have made an reimplementation of the earlier ideas of a patch. I have added two
new binary operators, div that is a integer division ({{#expr:74.33 / 4.44}}
results in 16.740990991, {{#expr:74.33 div 4.44}} gives 16), and fmod that is a
modulus of floats ({{#expr:74.33 fmod 4.44}} results in 3.29, {{#expr:74.33 mod
4.44}} gives 2).

Added three new unary operators, two to accompany the earlier changes, and one
that I think fits in the expr-handler, those are floor, ceil and abs.

attachment pfunc1.patch ignored as obsolete

AzaToth added a comment.Via ConduitNov 12 2006, 9:38 PM

updated patch

first of all, forgot to remove two statememnts, that I had used earlier, but
forgotted to remove. second, I have added sqrt and pow functions, so for
example {{#expr:sqrt(0.25^-1)}} will result in 2

attachment pfunc1.patch ignored as obsolete

AzaToth added a comment.Via ConduitNov 13 2006, 9:33 AM

changed div to idiv

As requested, changed the modification of div to an adition of 'idiv' for
integer division.

attachment pfunc1.patch ignored as obsolete

AzaToth added a comment.Via ConduitNov 13 2006, 10:47 AM

The full patch

changed implementation of integer divide to (int)(calc)

attachment pfunc1.patch ignored as obsolete

AzaToth added a comment.Via ConduitNov 13 2006, 10:47 AM

The full patch

changed implementation of integer divide to (int)(calc)

attachment pfunc1.patch ignored as obsolete

AzaToth added a comment.Via ConduitNov 13 2006, 4:43 PM

full patch

some cleanup, added checks for NaN, and added a workaround to be able to have
php-style numbers as input (12E07 etc...)

attachment pfunc1.patch ignored as obsolete

AzaToth added a comment.Via ConduitNov 13 2006, 6:35 PM

extended patch

this is the same as the previous patch, but with addition of sin, cos tan,
sinh, cosh, tanh, acos, asin, atan, log, ln and exp.

attachment pfunc2.patch ignored as obsolete

bzimport added a comment.Via ConduitNov 13 2006, 6:52 PM

robchur wrote:

What is the point in implementing all of these in wikitext?

AzaToth added a comment.Via ConduitNov 13 2006, 6:55 PM

(In reply to comment #20)

What is the point in implementing all of these in wikitext?

That's why I called it an extended patch, as it's not clear if the usual wiki
have any major use of them, but some wikis might have use for them.

bzimport added a comment.Via ConduitNov 13 2006, 6:57 PM

robchur wrote:

Hm. Might be worth implementing as another parser function extension, then,
since the existence of a patch implies a problem that needs to be solved, and
leaves an issue open where there isn't really one, if you see what I mean.

AzaToth added a comment.Via ConduitNov 13 2006, 7:04 PM

(In reply to comment #22)

Hm. Might be worth implementing as another parser function extension, then,
since the existence of a patch implies a problem that needs to be solved, and
leaves an issue open where there isn't really one, if you see what I mean.

To some extent I can see what you mean, the question that arise, would be if
it's a "Bad thing" to implement them, and the problem that would arise is that
the Expr-handler is rather atomic, so the code must then be duplicated.

bzimport added a comment.Via ConduitNov 14 2006, 2:58 AM

ayg wrote:

(In reply to comment #20)

What is the point in implementing all of these in wikitext?

Well, trigonometric functions would be invaluable for anyone using templates to
dynamically generate triangles of arbitrary dimensions. ;) (What sinh, cosh,
and tanh would be useful for, though, is beyond me, *especially* since you could
just use exp to generate them all . . .)

But hey, we're just talking switch statements, right? Why not go ahead and add
the whole math library? Shouldn't hurt performance at all, unless some are
processor-intensive/DOSable (which seems fairly unlikely, although I suppose
possible).

bzimport added a comment.Via ConduitNov 14 2006, 8:49 AM

robchur wrote:

It's not just about performance, though; it's about not changing wikitext into
something it isn't by adding lots of basically useless macros to it.

AzaToth added a comment.Via ConduitNov 14 2006, 9:27 AM

One usage for sinusoidal functions could be a unit circle:
<div style="position:relative; width: 600px; height: 600px;">
<div style="position:absolute; bottom: {{#expr:sin(0)*200+300}}px; left:
{{#expr:cos(0)*200+300}}px;">• 0</div>
<div style="position:absolute; bottom: {{#expr:sin(3.141592/6)*200+300}}px;
left: {{#expr:cos(3.141592/6)*200+300}}px;">• pi/6</div>
<div style="position:absolute; bottom: {{#expr:sin(3.141592/4)*200+300}}px;
left: {{#expr:cos(3.141592/4)*200+300}}px;">• pi/4</div>
<div style="position:absolute; bottom: {{#expr:sin(3.141592/3)*200+300}}px;
left: {{#expr:cos(3.141592/3)*200+300}}px;">• pi/3</div>
<div style="position:absolute; bottom: {{#expr:sin(3.141592/2)*200+300}}px;
left: {{#expr:cos(3.141592/2)*200+300}}px;">• pi/2</div>
<div style="position:absolute; bottom: {{#expr:sin(11*3.141592/6)*200+300}}px;
left: {{#expr:cos(11*3.141592/6)*200+300}}px;">• 11*pi/6</div>
<div style="position:absolute; bottom: {{#expr:sin(7*3.141592/4)*200+300}}px;
left: {{#expr:cos(7*3.141592/4)*200+300}}px;">• 7*pi/4</div>
<div style="position:absolute; bottom: {{#expr:sin(5*3.141592/3)*200+300}}px;
left: {{#expr:cos(5*3.141592/3)*200+300}}px;">• 5*pi/3</div>
<div style="position:absolute; bottom: {{#expr:sin(3*3.141592/2)*200+300}}px;
left: {{#expr:cos(3*3.141592/2)*200+300}}px;">• 3*pi/2</div>
<div style="position:absolute; bottom: {{#expr:sin(4*3.141592/3)*200+300}}px;
left: {{#expr:cos(4*3.141592/3)*200+300}}px;">• 4*pi/3</div>
<div style="position:absolute; bottom: {{#expr:sin(5*3.141592/4)*200+300}}px;
left: {{#expr:cos(5*3.141592/4)*200+300}}px;">• 5*pi/4</div>
<div style="position:absolute; bottom: {{#expr:sin(7*3.141592/6)*200+300}}px;
left: {{#expr:cos(7*3.141592/6)*200+300}}px;">• 7*pi/6</div>
<div style="position:absolute; bottom: {{#expr:sin(3.141592)*200+300}}px; left:
{{#expr:cos(3.141592)*200+300}}px;">• pi</div>
<div style="position:absolute; bottom: {{#expr:sin(5*3.141592/6)*200+300}}px;
left: {{#expr:cos(5*3.141592/6)*200+300}}px;">• 5*pi/6</div>
<div style="position:absolute; bottom: {{#expr:sin(3*3.141592/4)*200+300}}px;
left: {{#expr:cos(3*3.141592/4)*200+300}}px;">• 3*pi/4</div>
<div style="position:absolute; bottom: {{#expr:sin(2*3.141592/3)*200+300}}px;
left: {{#expr:cos(2*3.141592/3)*200+300}}px;">• 2*pi/3</div>
</div>

that will render this code:
<div style="position:relative; width: 600px; height: 600px;">
<div style="position:absolute; bottom: 300px; left: 500px;">• 0</div>

<div style="position:absolute; bottom: 399.999981132px; left: 473.20509165px;">•
pi/6</div>
<div style="position:absolute; bottom: 441.421333129px; left:
441.421379345px;">• pi/4</div>
<div style="position:absolute; bottom: 473.205058971px; left:
400.000037735px;">• pi/3</div>
<div style="position:absolute; bottom: 500px; left: 300.000065359px;">• pi/2</div>
<div style="position:absolute; bottom: 199.999792457px; left:
473.204960932px;">• 11*pi/6</div>
<div style="position:absolute; bottom: 158.578482008px; left:
441.421194482px;">• 7*pi/4</div>
<div style="position:absolute; bottom: 126.794810312px; left:
399.999811325px;">• 5*pi/3</div>
<div style="position:absolute; bottom: 100px; left: 299.999803923px;">• 3*pi/2</div>
<div style="position:absolute; bottom: 126.795006388px; left: 199.99984906px;">•
4*pi/3</div>

<div style="position:absolute; bottom: 158.578759302px; left:
158.578528223px;">• 5*pi/4</div>
<div style="position:absolute; bottom: 200.000132073px; left:
126.794842991px;">• 7*pi/6</div>
<div style="position:absolute; bottom: 300.000130718px; left: 100px;">• pi</div>
<div style="position:absolute; bottom: 400.000094338px; left:
126.794973709px;">• 5*pi/6</div>
<div style="position:absolute; bottom: 441.421425561px; left:
158.578713086px;">• 3*pi/4</div>
<div style="position:absolute; bottom: 473.20512433px; left: 200.00007547px;">•
2*pi/3</div>
</div>

bzimport added a comment.Via ConduitNov 14 2006, 5:14 PM

ayg wrote:

That's what images are for. Which is kind of the point of *not* adding this stuff.

AzaToth added a comment.Via ConduitNov 17 2006, 1:56 PM

Comment on attachment 2692
extended patch

Removing the "extended" patch, as I have created an third party extension
containing those functions instead

AzaToth added a comment.Via ConduitNov 17 2006, 11:36 PM

the full patch

the same patch, but now it dependednt on the patch to the other bug

attachment mof.patch ignored as obsolete

AzaToth added a comment.Via ConduitNov 18 2006, 1:11 PM

the full patch

missed the minmax from the other bug, fixed some indent also

attachment moddiv.patch ignored as obsolete

AzaToth added a comment.Via ConduitNov 18 2006, 1:13 PM

the full ptch

whoops, the wfMsg should be wfMsgForContent

attachment moddiv.patch ignored as obsolete

AzaToth added a comment.Via ConduitNov 18 2006, 10:51 PM

the patch again

things that where lost before

attachment moddiv.patch ignored as obsolete

AzaToth added a comment.Via ConduitNov 21 2006, 1:25 PM

the full patch

fixed the path to be patchable against reecent svn

Attached: minmaxfmodidivetc.patch

AzaToth added a comment.Via ConduitDec 2 2006, 2:09 PM

Tim Starling implied that this wouldn't be fixed as it would introduce a
floating point instruction to the code

Verdy_p added a comment.Via ConduitDec 12 2006, 2:11 AM

Hmmmm... there are ALREADY floatnig point instructions in the code
Just cnosider {{#expr:1/3}}, it already performs a floatting point division
using the floatting point operator / of PHP.
Note that PHP does not declare specifically the floating point variables and
numbers. They appear are necessary. That's why PHP's div performs a normal
division : there was historically no way in PHP to get the datatype of a
variable in PHP (today we can get the datatype of the value stored in a PHP var,
but we cannot decide which datatype will be used only by PHP programming, unless
we use some integer trucation functions).
Really, PHP cannot work without floating point support... That's why real
numbers are part of PHP's core and not of a separate PHP module.

Verdy_p added a comment.Via ConduitDec 22 2006, 1:32 AM

The last patch for the proposed "idiv" operator is still wrong;
it performs a (int)(a/b) operation which is limited to the various
caveats of conversion to (int), which is definitely not the mathematical
definition, is not cyclic,suffers of the problems near 0,rounds up for
negative numbers, and has value range limitations;
If you introduce floor() whynot using it?
i.e: floor(a/b)
Well if you provide floor, i'll use it instead of your proposed idiv;
otherwise i'll still need hacks to handle negative values.

Cyclic calculation is the base of any calendar computation, and this is
the calendric needs that first focused my attention; currently calendar
calculation in wikipedia require unnecessarily complex templates to perform
the correct calculation. But if we have the support for floor(), they will
be MUCH simpler, and floor() is really the most important thing what we need
to perform correct rounding, correct date calculation, and anyother type of
cyclic artithmetic. (All other modifications are not absolutely necessary as
they are basic inlined operations depending on floor() without needing tests
and too many instations of the template parameters).
For example:
a cdiv b == floor(a/b)
a cmod b == a-floor(a/b)*b

I proposed to implement floor as a "trunc n" operator like "round n":
a trunc n == floor(a*pow(10,n))/pow(10,n)

I am not proposing to implement the pow(x,y) operation, or exponential or
logarithms so pow(10,n) may be an internal lookup tableworking with n
as a small positive or negative integer.

However, given that PHP already depends on floating points, any floating
point library that supports floor(x) also supports exp(x) and pow(x,y),
and generally implements specially the case pow(10,y) where y is an
integer, for speed and precision.

Note that I also support the addition of the special "e" operator to allow
floating point numbers like "2.3e-12" which are already produced simply
with the current "*" and "/" operators!

Verdy_p added a comment.Via ConduitDec 22 2006, 1:33 AM

The last patch for the proposed "idiv" operator is still wrong;
it performs a (int)(a/b) operation which is limited to the various
caveats of conversion to (int), which is definitely not the mathematical
definition, is not cyclic,suffers of the problems near 0,rounds up for
negative numbers, and has value range limitations;
If you introduce floor() whynot using it?
i.e: floor(a/b)
Well if you provide floor, i'll use it instead of your proposed idiv;
otherwise i'll still need hacks to handle negative values.

Cyclic calculation is the base of any calendar computation, and this is
the calendric needs that first focused my attention; currently calendar
calculation in wikipedia require unnecessarily complex templates to perform
the correct calculation. But if we have the support for floor(), they will
be MUCH simpler, and floor() is really the most important thing what we need
to perform correct rounding, correct date calculation, and anyother type of
cyclic artithmetic. (All other modifications are not absolutely necessary as
they are basic inlined operations depending on floor() without needing tests
and too many instations of the template parameters).
For example:
a cdiv b == floor(a/b)
a cmod b == a-floor(a/b)*b

I proposed to implement floor as a "trunc n" operator like "round n":
a trunc n == floor(a*pow(10,n))/pow(10,n)

I am not proposing to implement the pow(x,y) operation, or exponential or
logarithms so pow(10,n) may be an internal lookup tableworking with n
as a small positive or negative integer.

However, given that PHP already depends on floating points, any floating
point library that supports floor(x) also supports exp(x) and pow(x,y),
and generally implements specially the case pow(10,y) where y is an
integer, for speed and precision.

Note that I also support the addition of the special "e" operator to allow
floating point numbers like "2.3e-12" which are already produced simply
with the current "*" and "/" operators!

Verdy_p added a comment.Via ConduitDec 22 2006, 1:44 AM

note that i am not sure we really need trigonometric functions;
unlike calendar calculation which are needed or genertal maintenance
of wikipedia, notably to generate links or prepare forms, trigonometry
finds its application only to compute images, and this is needed only
for internal SVG support. I can't see any application where trigonometry
would be needed to create links to other pages depending on parameters:
if all fits on the same page, this sould be precomputed outside of the
wiki syntax.

(well I see some exceptions now: astronomic and geodesic calculation for example
to compute external links to geographic datadepending on longitude/latitude,
or to compute projections and astronomic positions for computing the islamic
calendar, or the traditional Chinese calendar; but before that, we need
some demonstrations with working formulas that can't be written without them)

bzimport added a comment.Via ConduitDec 22 2006, 1:53 AM

ayg wrote:

Pfft, no such thing as something that *needs* trig functions. After all, a good
approximation of sin x for reasonable-sized x is x + x*x*x/6 + x*x*x*x*x/120 +
x*x*x*x*x*x*x/5040 + x*x*x*x*x*x*x*x*x/362880 + x*x*x*x*x*x*x*x*x*x*x/39916800 +
x*x*x*x*x*x*x*x*x*x*x*x*x/6227020800 +
x*x*x*x*x*x*x*x*x*x*x*x*x*x*x/1307674368000. That'll probably get you nearly
indistinguishable results for within 3π or 4π around the origin. And if you
need more precision, you can go on like that. Who needs an explicit sine
function? ;)

http://en.wikipedia.org/wiki/Image:Taylorsine.svg

Verdy_p added a comment.Via ConduitDec 22 2006, 9:37 AM

I did not ask for trigonometric functions support! Reread!
I am asking for a way to solve the unnecessarily complex templates used to
workaround the severe issues in the round and mod operator, and the only urgent
need is for a correct support of floor(), i.e. not depending on conversion to
integer with a (int) typecast of PHP; with floor,lots of unnecessarily complex
formulastrying to workaround with the current "round" operator will be solved
much more nicely than they are now.

And no, I won't use any form of limited development of sin(x) for small values
of x like you propose: the operand will be instanciated too many times, causing
the template to exhaust server memory resources very soon! Your "solution" for a
problem I did not ask for is extremely bad and won't work reliably as long as
#expr expressions will not support assignment to temporary work variables to
avoid multiple instances of the template argument!
Here I mean: as long as we can't write your limited dev.function as the
following template, it should never be used!:
{{#expr:

 (x:=({{{1}}}))
+ x*x*x/6
+ x*x*x*x*x/120
+ x*x*x*x*x*x*x/5040
+ x*x*x*x*x*x*x*x*x/362880
+ x*x*x*x*x*x*x*x*x*x*x/39916800
+ x*x*x*x*x*x*x*x*x*x*x*x*x/6227020800
+ x*x*x*x*x*x*x*x*x*x*x*x*x*x*x/1307674368000

}}
Note above the syntax using ":=" to assign a computed value to a named variable
x: that's the only way we can avoid too many instances and substitutions of the
template parameter, and to solve the extreme memory allocation problem for such
expression. Without such system, which is extremely simple to implement in PHP
using an associative array of variable names (we can limit variable names to
single letters [a-z], or even more to [a-di-km-np-z]!) I will never create such
expressions with the wiki syntax!

Verdy_p added a comment.Via ConduitDec 22 2006, 9:41 AM

And your fomula is wrong! you forgot the sign changes! Reread your own reference!

bzimport added a comment.Via ConduitDec 22 2006, 3:43 PM

ayg wrote:

(In reply to comment #40)

I did not ask for trigonometric functions support! Reread!
. . .
And no, I won't use any form of limited development of sin(x) for small values
of x like you propose: the operand will be instanciated too many times, causing
the template to exhaust server memory resources very soon!

I was joking. Thence the ";)". Although I did try it at
[[User:Simetrical/sine]] to see if it would work, which it did. And yes, I
spotted the issue with the signs. Never mind me.

Verdy_p added a comment.Via ConduitDec 24 2006, 12:58 AM

You should really factorize the common factors! It will save lots of instances of ({{{1}}}) in your test
template... Yes it will require some parenthesis pairs, but the cost of parenthesis is insignificant face to the
memory cost on the server with so many instances of ({{{1}}}). Instead of having 1+3+5+7+9+11+13+15=64 instances,
you'll have only 15 instances of the template parameter (one for each degree of the polynomial); remember that if
parameter 1 is long, this will save about 75% of the total string length! Factorization is extremely easy given
the nature of the constants which are simple factorials growing with the degree. The additional benefit is also a
better precision of the result because the smallest elements are added together before being multiplied to the
next degree and added to the next (larger) elements. You also save stack space and the final recursion for the
evaluation of the complete expression, and will save lots of operations.

Here is the equivalent formula at degree 15:
{{#expr:
(1-(1-(1-(1-(1-(1-(1-
({{{1}}})*({{{1}}})/210)*
({{{1}}})*({{{1}}})/156)*
({{{1}}})*({{{1}}})/110)*
({{{1}}})*({{{1}}})/72)*
({{{1}}})*({{{1}}})/42)*
({{{1}}})*({{{1}}})/20)*
({{{1}}})*({{{1}}})/6)*
({{{1}}}) round 5}}

bzimport added a comment.Via ConduitDec 24 2006, 3:20 AM

nygreen wrote:

disregarding the trigonometric discussion, I see the need for a working mod and
floor functions. Integer divisjon is easy to solve with trunc(x/y). I suggest
using the fix that adds the fmod and floor functions (as in PHP), and leave the
current mod function as it is (compatible with php)

Verdy_p added a comment.Via ConduitDec 24 2006, 4:28 AM

I do agree: don't change any existing operators as this may break compatibility, possibly requiring lots of editsto
verify the various expressions. fmod is not absolutely needed as it can be implemented using floor; the same is true
for the true integer division. Let's just have a working floor function, and almost all existing difficulties caused
by unnecessarily complex expressions with workaround hacks will disappear.

I also support the addition of the operator "E" (for example 1E-4=0.0001), or extending the syntaxrecognizer so that
it will parse numbers in scientific notation without error! The main reason for this addition is the fact that #expr
returns numbers in scientific notation like 9.99E-5 (i.e. for all numbers lower than 0.0001 in absolute value after
default rounding when formating numbers as strings!). This is THE major cause of templates returning unexpected
syntax errors (can't parse "E"!) because the result of #expr (returned by a subtemplate) is often used in other
#expr expressions! Because of this limitation, we have to substitute a lot of subtemplates and then replace
embedded "{{#expr:...}}" by "(...)" after substitution of subtemplates.

Verdy_p added a comment.Via ConduitDec 24 2006, 4:44 AM

For a working sine template (which works with any input value you can see [[en:Template:sin]]. This is an example
where a working fmod or floor would greatly simplify the expression! The limitation of precision to 4 digits on
output is also caused by the absence of support for input numbers like "1E-5" (and the main reason we need a hack to
support [[en:Template:Mod]]); this example is also a good case where we need to fully subtitute {{Mod}} to replace
{{#expr:...}} by (...) in the substituted expressionto avoid errors on output due to absence of support
(otherwise, "{{sin|0.00001}}" would return "1E-5" if we allow 5 digits in output precisionfor this function.
Look also at how the Mod template requires:

  • 7 instances (!) of its first input parameter instead of just 1
  • 5 instances (!) of the second parameter instead of just 1, and
  • quite complex "#ifexpr:" hacks to workaround the current problems in "mod" and "round" operators.

Calendar templates also require such complex substitution, and then using unnecessarily complex use of
existing "mod" operator. This would be much simpler with the support of floor. The same is true for conversion of
geographic coordinates fromdecimal to degrees,minutes,seconds (here also we need a working fmod simply based on
floor).

Verdy_p added a comment.Via ConduitDec 24 2006, 4:54 AM

The trigonometric circle works! Type this in English Wikipedia:
<div style="position:relative;width:600px;height:600px">
<div style="position:absolute;bottom:{{#expr:{{sin|0}}*200+300}}px;left:{{#expr:{{cos|0}}*200+300}}px">• 0</div>
<div style="position:absolute;bottom:{{#expr:{{sin|3.141592/6}}*200+300}}px;left:{{#expr:{{cos|3.141592/6}}*200+300}}
px">• pi/6</div>
<div style="position:absolute;bottom:{{#expr:{{sin|3.141592/4}}*200+300}}px;left:{{#expr:{{cos|3.141592/4}}*200+300}}
px">• pi/4</div>
<div style="position:absolute;bottom:{{#expr:{{sin|3.141592/3}}*200+300}}px;left:{{#expr:{{cos|3.141592/3}}*200+300}}
px">• pi/3</div>
<div style="position:absolute;bottom:{{#expr:{{sin|3.141592/2}}*200+300}}px;left:{{#expr:{{cos|3.141592/2}}*200+300}}
px">• pi/2</div>
<div style="position:absolute;bottom:{{#expr:{{sin|11*3.141592/6}}*200+300}}px;left:{{#expr:{{cos|11*3.141592/6}}
*200+300}}px">• 11*pi/6</div>
<div style="position:absolute;bottom:{{#expr:{{sin|7*3.141592/4}}*200+300}}px;left:{{#expr:{{cos|7*3.141592/4}}
*200+300}}px">• 7*pi/4</div>
<div style="position:absolute;bottom:{{#expr:{{sin|5*3.141592/3}}*200+300}}px;left:{{#expr:{{cos|5*3.141592/3}}
*200+300}}px">• 5*pi/3</div>
<div style="position:absolute;bottom:{{#expr:{{sin|3*3.141592/2}}*200+300}}px;left:{{#expr:{{cos|3*3.141592/2}}
*200+300}}px">• 3*pi/2</div>
<div style="position:absolute;bottom:{{#expr:{{sin|4*3.141592/3}}*200+300}}px;left:{{#expr:{{cos|4*3.141592/3}}
*200+300}}px">• 4*pi/3</div>
<div style="position:absolute;bottom:{{#expr:{{sin|5*3.141592/4}}*200+300}}px;left:{{#expr:{{cos|5*3.141592/4}}
*200+300}}px">• 5*pi/4</div>
<div style="position:absolute;bottom:{{#expr:{{sin|7*3.141592/6}}*200+300}}px;left:{{#expr:{{cos|7*3.141592/6}}
*200+300}}px">• 7*pi/6</div>
<div style="position:absolute;bottom:{{#expr:{{sin|3.141592}}*200+300}}px;left:{{#expr:{{cos|3.141592}}*200+300}}
px">• pi</div>
<div style="position:absolute;bottom:{{#expr:{{sin|5*3.141592/6}}*200+300}}px;left:{{#expr:{{cos|5*3.141592/6}}
*200+300}}px">• 5*pi/6</div>
<div style="position:absolute;bottom:{{#expr:{{sin|3*3.141592/4}}*200+300}}px;left:{{#expr:{{cos|3*3.141592/4}}
*200+300}}px">• 3*pi/4</div>
<div style="position:absolute;bottom:{{#expr:{{sin|2*3.141592/3}}*200+300}}px;left:{{#expr:{{cos|2*3.141592/3}}
*200+300}}px">• 2*pi/3</div>
</div>

that will render this code:

<div style="position:relative;width:600px;height:600px">
<div style="position:absolute;bottom:300px;left:500px">• 0</div>
<div style="position:absolute;bottom:400px;left:473.2px">• pi/6</div>
<div style="position:absolute;bottom:441.42px;left:441.42px">• pi/4</div>
<div style="position:absolute;bottom:473.2px;left:400px">• pi/3</div>
<div style="position:absolute;bottom:500px;left:300px">• pi/2</div>
<div style="position:absolute;bottom:200px;left:473.2px">• 11*pi/6</div>
<div style="position:absolute;bottom:158.58px;left:441.42px">• 7*pi/4</div>
<div style="position:absolute;bottom:126.8px;left:400px">• 5*pi/3</div>
<div style="position:absolute;bottom:100px;left:300.02px">• 3*pi/2</div>
<div style="position:absolute;bottom:126.8px;left:200px">• 4*pi/3</div>
<div style="position:absolute;bottom:158.58px;left:158.58px">• 5*pi/4</div>
<div style="position:absolute;bottom:200px;left:126.8px">• 7*pi/6</div>
<div style="position:absolute;bottom:300px;left:100px">• pi</div>
<div style="position:absolute;bottom:400px;left:126.8px">• 5*pi/6</div>
<div style="position:absolute;bottom:441.42px;left:158.58px">• 3*pi/4</div>
<div style="position:absolute;bottom:473.2px;left:200px">• 2*pi/3</div>
</div>

bzimport added a comment.Via ConduitDec 24 2006, 4:58 AM

robchur wrote:

Please can all further discussion on this closed bug be limited to:

  • Reasons it should be reopened and fixed
  • What the fixes should be
  • Implementation notes

We do NOT need to know about hacks that will allow us to draw circles in
wikitext; a demonstration of such abuse of parser functions is more inclined to
turn us off the whole idea. In addition, to be frank, this is a bug tracker, not
a mathematical debate forum.

Since there is a hell of a lot of irrelevant discussion here, I would recommend
that if a clear and concise bug report can be opened, detailing what's needed,
then one is opened fresh.

Verdy_p added a comment.Via ConduitDec 26 2006, 2:00 PM

I already summarized the need, read above. This was just a reply to show that the support for trigonometric
functions is not necessary, unlike a correct support for:

  • support of floor() for correct rounding (possible syntax: "x trunc 0"). This cleanly solves the DIV and MOD

problem, and as well, the problem of cyclic arithmetic.

  • the E operator (to put an end to expression evaluation errors caused by numbers computed by #expr that are

formated in scientific exponential notation, like "9E-5" instead of "0.00009"; for now all that can be done is to
avoid rounding the #expr result with more than 4 decimals, using "x round 4" but not "x round 5"). This notation
couldbesupported either lexically (accepting input numbers like "1E-5") or as an operator if the current lexical
scanner should not be changed (computing the result of "x E y" as "x*pow(10,y)")

  • possibly adding optional parameter(s) to #expr to specify the output format: "{{#expr:some expression|f=%.5f}}" to

force 5 decimals (rounding already occurs), "{{#expr:some expression|.=,}}" to set the decimal
parameter, "#expr:some expression|lang=fa}} to use locale conventions for numbers (including the correct digits for
that language)... Note that using #expr-computed expressions in CSS values generally does not work if it is returned
in scientific notation. Formatting numbers often requires many reevaluation of the input expression, meaning that
there are many instances of the input parameter, and this severaly affects the server performance due to the extra
memory space taken by repeated template parameter strings!

  • implement in the server a cache for template parameters, and not substituting them until they are actually used

(for example expressions using input parameters in #if and #ifexpr should not be substituted immediately until they
are actuelly used in one of the then or else clauses. And substitutions should not require reevaluating the content:
the parameter may be another #expr, whose evaluation is already computed and stored in a cache so that you know
that "{{{1}}}" will already be completely expanded and precomputed as "12.345", instead of the effective expression,
and this result is then simply reused as is on next instances of "{{{1}}}".) The current full substitution of all
template parameters before the template invokation is actually evaluated is a severe waste of server resources.

  • implement some support for storing intermediate #expr expression results in single-letter variables (except "e"

or "E" used for the scientific notation, see above): this reduces a lot the memory requirement, and makes expression
much easier to read and debug, and much faster to compute with much less memory and CPU overhead for each instance
of common sub-expressions. Note that in order to work, the expression evaluation order (of operands) must remain
fully predictive, always from left to right, this guarantees that intermediate assignment work as expected, but
unused then or else clauses in #if will not necessarily evaluated, but simply skipped.

Verdy_p added a comment.Via ConduitSep 30 2009, 7:39 AM

the INT_DIVIDE operator (idiv) is still wrong in the final patch, as it uses the formula:

$stack[] = (int)($left / $right);

which overflows the too small capacity of ints.

Note that the parameters $left and $right can already be floatting points, so the division results in a floatting point, but the typecast to (int) gets a wrong result. Well, at least we could rewrite the formula using "floor(x/y)" in templates instead of "x idiv y", and in that case, the way "idiv" works should be either "floor(floor(x)/floor(y))" OR "(int)(x)/(int)(y)", but NOT the way as it is written that mixes everything. But these two solutions would break existing code that depend on "idiv" to continue getting the result from the division of two floaating points without rounding them down to an integer before the division.

For this reason, it should really be:

$stack[] = floor($left / $right);

However this would even change the behavior of "idiv" if the result of the division is negative, because the typecast to int does not really uses floor, but truncates towards zero. So the effective change should be:

$left = $left / $right;
$stack[] = ($left < 0) ? ceil($left) : floor($left);

This correction will preserve ALL result values that are already correct with the current implementation (truncating the result of the floatting point division to the nearest integer towards zero), but it will extend the usage of "idiv" to cover a wider range of values than just the native binary integers.

I can't understand that implementers are not thinking about the coherence of numeric operations and datatypes, when they finally implement things the wrong way to solve a floating point problem : floatting points values are NOT interchangeable with native integer values, and typecasts to (int) is a wellknown source of bugs in many programs, because of lack of experience of developpers !

I've seen such error frequently even in C or C++ where ALL variables types are declared with float (or double), but with a formula using incorrectly a typecast with (int) instead of "floor()". This same error occurs once again here... When developing a software with global usage, I can assert that this stupid bug is a result of incompetence (i.e. lack of training or experience).

Verdy_p added a comment.Via ConduitSep 30 2009, 7:39 AM

the INT_DIVIDE operator (idiv) is still wrong in the final patch, as it uses the formula:

$stack[] = (int)($left / $right);

which overflows the too small capacity of ints.

Note that the parameters $left and $right can already be floatting points, so the division results in a floatting point, but the typecast to (int) gets a wrong result. Well, at least we could rewrite the formula using "floor(x/y)" in templates instead of "x idiv y", and in that case, the way "idiv" works should be either "floor(floor(x)/floor(y))" OR "(int)(x)/(int)(y)", but NOT the way as it is written that mixes everything. But these two solutions would break existing code that depend on "idiv" to continue getting the result from the division of two floaating points without rounding them down to an integer before the division.

For this reason, it should really be:

$stack[] = floor($left / $right);

However this would even change the behavior of "idiv" if the result of the division is negative, because the typecast to int does not really uses floor, but truncates towards zero. So the effective change should be:

$left = $left / $right;
$stack[] = ($left < 0) ? ceil($left) : floor($left);

This correction will preserve ALL result values that are already correct with the current implementation (truncating the result of the floatting point division to the nearest integer towards zero), but it will extend the usage of "idiv" to cover a wider range of values than just the native binary integers.

I can't understand that implementers are not thinking about the coherence of numeric operations and datatypes, when they finally implement things the wrong way to solve a floating point problem : floatting points values are NOT interchangeable with native integer values, and typecasts to (int) is a wellknown source of bugs in many programs, because of lack of experience of developpers !

I've seen such error frequently even in C or C++ where ALL variables types are declared with float (or double), but with a formula using incorrectly a typecast with (int) instead of "floor()". This same error occurs once again here... When developing a software with global usage, I can assert that this stupid bug is a result of incompetence (i.e. lack of training or experience).

Verdy_p added a comment.Via ConduitSep 30 2009, 7:43 AM

the INT_DIVIDE operator (idiv) is still wrong in the final patch, as it uses the formula:

$stack[] = (int)($left / $right);

which overflows the too small capacity of ints.

Note that the parameters $left and $right can already be floatting points, so the division results in a floatting point, but the typecast to (int) gets a wrong result. Well, at least we could rewrite the formula using "floor(x/y)" in templates instead of "x idiv y", and in that case, the way "idiv" works should be either "floor(floor(x)/floor(y))" OR "(int)(x)/(int)(y)", but NOT the way as it is written that mixes everything. But these two solutions would break existing code that depend on "idiv" to continue getting the result from the division of two floaating points without rounding them down to an integer before the division.

For this reason, it should really be:

$stack[] = floor($left / $right);

However this would even change the behavior of "idiv" if the result of the division is negative, because the typecast to int does not really uses floor, but truncates towards zero. So the effective change should be:

$result = $left / $right;
$stack[] = ($result < 0) ? ceil($result) : floor($result);

This correction will preserve ALL result values that are already correct with the current implementation (truncating the result of the floatting point division to the nearest integer towards zero), but it will extend the usage of "idiv" to cover a wider range of values than just the native binary integers.

I can't understand that implementers are not thinking about the coherence of numeric operations and datatypes, when they finally implement things the wrong way to solve a floating point problem : floatting points values are NOT interchangeable with native integer values, and typecasts to (int) is a wellknown source of bugs in many programs, because of lack of experience of developpers !

I've seen such error frequently even in C or C++ where ALL variables types are declared with float (or double), but with a formula using incorrectly a typecast with (int) instead of "floor()". This same error occurs once again here... When developing a software with global usage, I can assert that this stupid bug is a result of incompetence (i.e. lack of training or experience).

Verdy_p added a comment.Via ConduitOct 17 2009, 2:33 AM

Note that I have received several emails from various users (including admins from non MediaWiki sites) confirming that this is a bug: they saw my last comment (sorry if it appears 3 times just above), and ask me if the bug is corrected, or when it will be corrected...

Can you then apply my suggested correction (which tests the sign of the result) at end of the inserted lines at 404-409 of your last published patch ?

Or do we have to live just with the now existing "floor()" function and use it directly in our {{#expr:}} expressions instead of the bogous IDIV operator (note that the floating-point modulo operator is correct, as it uses fmod() to compute the value) ?

Aklapper added a comment.Via ConduitJun 2 2012, 9:30 AM

Based on comment 50 I replace the keyword "patch-need-review" by "patch-reviewed" - the patch needs rework and volunteers are welcome!
Also moving to "ParserFunctions" component as that's what the patch is for.

ori added a comment.Via ConduitDec 11 2012, 11:28 AM

Note that I32c9eca6 changes the modulo operator so that it handles floating point values properly.

Verdy_p added a comment.Via ConduitDec 12 2012, 1:28 AM

The patch found in I32c9ca6 incorrectly casts its parameters to (float) instead of (double). This means that it reduces their precision when they are double.

Note that the fmod() PHP function takes double parameters (not float parameters), so the cast to (float) is immediately recasted by promotion to (double).

Please use typecasts to (double) directly to keep the precision and avoid roundings.

ori added a comment.Via ConduitDec 12 2012, 5:49 AM

Gerrit change 38278 casts to double, but I note that parser function aficionados are better served by helping midwife Scribunto (Lua templates) on major wikis.

Verdy_p added a comment.Via ConduitDec 12 2012, 9:32 PM

One example demontrates the difference:

  • {{#expr: 0.9900000001 -floor( 0.9900000001 / 0.03 )
    • 0.03 }}

::
:: This uses PHP's fmod() function but arguments are left as
:: double, no rounding occurs and precision is kept
:: Expected value: 1E-10 with 8 digits of precision
:: The result is: 1.0000000827404E-10
:: (excellent order of magnitude and precision)

  • {{#expr: 0.9900000001 mod 0.03 }}

::
:: This uses PHP's fmod() function but arguments are incorrectly
:: downcasted to float, forcing rounding and loss of precision.
:: Expected value: 1E-10 with 8 digits of precision
:: The result is: 4.4408920985006E-16
:: (bad: 6 orders of magnitude lost, out of precision)

  • {{#expr: (2*PI) -floor( (2*PI) / (PI/6) )
    • (PI/6) }}

::
:: Expected value: 0 with an absolute error not exceeding PI/2*1E-14
:: Effective result: 0
:: (excellent, but could be by chance; for other divisors set to (PI/N), where N is an odd prime, the max error of PI/2/N*1E-14 is respected)

  • {{#expr: (2*PI) mod (PI/6) }}

::
:: Expected value: 0 with an absolute error not exceeding PI/2*1E-14
:: Effective result: 1.0000003602961E-10
:: (very bad, the absolute error is too large by a factor of about 1E7)

Reedy added a comment.Via ConduitDec 27 2012, 12:50 AM

Is this fixed now?

Verdy_p added a comment.Via ConduitDec 27 2012, 1:22 PM

No, this is worse now: the tow cases above that were bad in precision no longer display anything, so {{#expr: 0.9900000001 mod 0.03 }} returns now an empty string! This is most probably not a pronlem of the operator itself, but of the number to string conversion, which performs incorrect rounding and removes all digits (not keeping at least a single zero).

Verdy_p added a comment.Via ConduitDec 27 2012, 1:25 PM

In other words you've got a new regression.
Tested on Meta, see http://meta.wikimedia.org/wiki/Template_talk:YMD2MJD#Empty_output_with_denormal_numbers

Verdy_p added a comment.Via ConduitDec 27 2012, 1:35 PM

The result is always correct when using PHP's and MEdiawiki's floor(), but not when using PHP's fmod().
May be it is PHP's fmod() which is bogous, and that returns a NaN double whose output is an empty string. Couldn't you just use PHP's floor() instead to implement the Mediawiki's MOD operator ?

For now I'll stick on using floor() for ALL cyclic computations. MOD is completely broken and unreliable.

Really, you should be more aware of basic rounding modes (towards zero, for the symetry around zero, or towards minus infinity for cyclic uses). The maths' MOD uses floor() for cyclic computations; the financial's MOD uses trunc() for performing roundings). The IEEE scientific MOD uses rounding towards the nearest even number (in order to balance rounding errors).

Anomie added a comment.Via ConduitDec 28 2012, 9:54 PM

A few notes:

PHP doesn't have different-precision floating point types, "float" and "double" are the same. Both are implemented in terms of a C double, which is probably going to be an IEEE 754 64-bit representation.

On my local test wiki, {{#expr: 0.9900000001 mod 0.03 }} returns 1.0000003602961E-10 both before and after change 38278 is applied. Similarly, {{#expr: (2*PI) mod (PI/6) }} returns 4.4408920985006E-16 both with and without change 38278. I don't know what you were doing to get those different results.

As for the situation now, note that the extension has been rolled back on WMF wikis to a version before I32c9ca6 due to many templates explicitly relying on the old integer-casting behavior of 'mod'. So the result of 0.9900000001 mod 0.03 is actually coming out as boolean false due to division by zero, which winds up being displayed as an empty string.

Gerrit change I6114c6e7 reverts the behavior of 'mod' while still fixing bug 35866, and at the same time adds a new 'fmod' with the floating-point behavior requested here.

ori added a comment.Via ConduitApr 15 2013, 4:48 PM

It is proper to implement this using Lua / Scribunto now, I think. Should we close this?

MZMcBride added a comment.Via ConduitApr 16 2013, 1:26 AM

(In reply to comment #64)

It is proper to implement this using Lua / Scribunto now, I think. Should we
close this?

It seems reasonable enough to me to mark this as resolved/fixed now (particularly with Gerrit change I6114c6e7 [which introduced fmod] now merged).

I'll go ahead and cautiously mark this as resolved/fixed.

Philippe or anyone else: if you disagree with this resolution, please don't hesitate to re-open this bug report (or file a new bug). I'm not sure if all fo the people commenting here have had a chance to check out Scribunto/Lua, but it's much fancier and more robust than ParserFunctions + #expr. :-)

Add Comment