another contest

[fir]

im a bit lazy and tired recently and dont act actively recently last few days but this contest was kinda fun (and succesful; in this way that it make many people to act in it and response)

i suggest to do some other like 2 or 3 weaks from now, only you need to discuss some possible topic for it... so?

(maybe something that would need a bit of dose of creativity maybe not very strict output? i suggest maybe something that would get c sources as an input and maybe do some analysis or something like that?) or maybe something other?

(this contest shouldnt be too soon as people could get bored and weary of it (like me today generally weary and bored) but after some weeks? maybe its good idea )

[fir]

there are also possible interesting topics to read into solution though im not sure if i would do code them myself

1) own implementation of printf (to eventually get rid dependency of msvcrt
(hovever im not sure if other dependencies woule make me still tie to it)
and have printf fully flexible and customizable

2) small library for basic bignum (N*long) arithmetic

[luser droog]

I agree. The recent wildcard challenge from Anton was a lot of fun, appeared
to attract a lot of participation, and revitalized the on-topic discussions
here.

I think one of the virtues of the wildcard matching function is its limited
scope. It wasn't too big. I think printf is too big. But I think something
smaller like atoi() or itoa() might be good.

In another post you suggested a bignum library. I think that one is also
too big. But a single function from such a library like add() or mul()
might be good. Especially if the argument types are limited, like
multiplying a bignum with a long or an int. Or adding two bignums.

So I suggest sticking with the "single function interface" for such
challenges. Of course, these are all just my opinion. I welcome any
well-argued disagreement.

--
loosur druug

[fir]

W dniu czwartek, 30 sierpnia 2018 02:06:45 UTC+2 użytkownik luser droog napisał:
> On Tuesday, August 28, 2018 at 1:15:15 PM UTC-5, fir wrote:
> > im a bit lazy and tired recently and dont act actively recently last few days but this contest was kinda fun (and succesful; in this way that it make many people to act in it and response)
> >
> > i suggest to do some other like 2 or 3 weaks from now, only you need to discuss some possible topic for it... so?
> >
> > (maybe something that would need a bit of dose of creativity maybe not very strict output? i suggest maybe something that would get c sources as an input and maybe do some analysis or something like that?) or maybe something other?
> >
> > (this contest shouldnt be too soon as people could get bored and weary of it (like me today generally weary and bored) but after some weeks? maybe its good idea )
>
> I agree. The recent wildcard challenge from Anton was a lot of fun, appeared
> to attract a lot of participation, and revitalized the on-topic discussions
> here.
>

ye that was a surprise, becouse this group as i remember it before was not much 'movable' to do anything

this group overally improved a bit in recent times (maybe thet taken my words
on needed renovation ;c [still its to more foam making and to lack of real coding, but a bit better]

> I think one of the virtues of the wildcard matching function is its limited
> scope. It wasn't too big. I think printf is too big. But I think something
> smaller like atoi() or itoa() might be good.
>
> In another post you suggested a bignum library. I think that one is also
> too big. But a single function from such a library like add() or mul()
> might be good. Especially if the argument types are limited, like
> multiplying a bignum with a long or an int. Or adding two bignums.
>
> So I suggest sticking with the "single function interface" for such
> challenges. Of course, these are all just my opinion. I welcome any
> well-argued disagreement.
>

ye i know this might be a bit big (thats why im not sure if i would participate, hovever results of it could be usefull if publicited as public domain to use for anyone (that should be necessary imo)

itoa/atoi hovever could be a bit to small* and if you wnt one arithmetic operation better maybe get division (a bit more usefull to see that)

* hovever maybe still usable as i dont even remember if i got my own implementation somewhere

not sure if printf is such big asp if you dont want to cover fully 'all' but what you generally just use

> --
> loosur druug

[fir]

in fact after rethinking i think this bignum contest would be quite good

quite interesting becouse when you
would do that you would need to make
a couple of interesting design
decissions

if you would limit yourself to only
integer bignums (i mean not even fixed
points just integer) it seems not to big
as topic

you would need to implement + - * / and also possibly % and atoi and itoa for this (i mean converstion to and form text numeber form)

i could participate... im not even sure i i just could do it alone, but if someone would participate it could be more fun for group

[Anton Shepelev]

fir:

>small library for basic bignum (N*long) arithmetic

Am I wrong in thinking that a trivial implementation is
possible that stores numbers as byte arrays and treats them
numbers in base 256? Futhermore, one may encode rational
numbers losslessly storing numerator and denominator
separately as such bignums.

--
() ascii ribbon campaign - against html e-mail
/\ http://preview.tinyurl.com/qcy6mjc [archived]

[Thiago Adams]

On Friday, August 31, 2018 at 10:51:20 AM UTC-3, fir wrote:
> in fact after rethinking i think this bignum contest would be quite good

I already have my code for that and it is online. :)

[fir]

W dniu piątek, 31 sierpnia 2018 16:15:02 UTC+2 użytkownik Anton Shepelev napisał:
> fir:
>
> >small library for basic bignum (N*long) arithmetic
>
> Am I wrong in thinking that a trivial implementation is
> possible that stores numbers as byte arrays and treats them
> numbers in base 256? Futhermore, one may encode rational
> numbers losslessly storing numerator and denominator
> separately as such bignums.
>

obviously it is possible (though its not necessary best form, i for example would maybe rather keep values from 0 to 1e9 in array of integers, maybe - to make atoi/itoa more asier and somputations faster, i said maybe becouse probbaly no, i mean maybe it would show its better to stick to something other)

no nominator/denominator i think pure integers could be enough as start)

you may procclaim/announce this kind of contest if you want and if you got some
strength to move this group to it ;c i possibly could parcitipate in this if some persons would join (as to doing it alone im not sure if i would do, but as a contest quite probably - though this
time i also could say, i wouldnt go myself for any kind of winning just would like to go cheep and easy way, so? )

[David Brown]

On 31/08/18 16:14, Anton Shepelev wrote:
> fir:
>
>> small library for basic bignum (N*long) arithmetic
>
> Am I wrong in thinking that a trivial implementation is
> possible that stores numbers as byte arrays and treats them
> numbers in base 256? Futhermore, one may encode rational
> numbers losslessly storing numerator and denominator
> separately as such bignums.
>

No, that is not wrong at all. That is the basic way to do it.

Everything beyond that is a matter of efficiency (such as using larger
blocks than 8-bit), algorithms (especially for multiplication and
division), memory optimisation (minimising allocations, cache line
alignment), make use of cpu's SIMD instructions, and of course finding
the most convenient programmer interface (C++ anyone?).

Another contest is not a bad idea, but I don't think a bignum library is
a good choice. (I don't have a better choice as yet.)

[Rick C. Hodgin]

On 8/31/2018 10:41 AM, David Brown wrote:
> Another contest is not a bad idea, but I don't think a bignum library is
> a good choice. (I don't have a better choice as yet.)

I agree. If you're going to limit bignum to integer, it won't be
too bad. But if you allow arbitrary precision floating point, you
are opening up a huge can of complex worms.

I think another contest would be desirable.

--
Rick C. Hodgin

[fir]

hovever i can add there is some doubt here:

this doubt is becouse if you state a topic/quest you need to state it precisely, i mean it would be weird if
anybody would use its own 'form' of such big integer

this meand such code should work on some
standarized numbers, like i mean N*32bits
ram data where N*32 bits set to 1 mean -1
N*32 bits set to zero mean 0

OR you should define the task as just taking various length of numbers in text forms like "1296087162876129378612938" 8 "3876387683763"

[fir]

maybe the second would be better i mean
wrote routines that just get such numerical strings and gives results in such form of numerical string to

the first form would more enforced binary form and taht is maybe a bit unfortunate,
becouse i wouled maybe at first would better like how to know that before knowing how to optimise that to pure binary form ;c, so?


still not saying its immediately easy etc, but maybe worth tryin?

[hovever it still an option to allow this for someone to do it any way he needs, too, this is also an option]

[fir]

ye, if doing that probably that form of contest should be suitable:

wrote a tiny library of functions
that take integer numbers like this

"38763876387637863" * "-29729872987298729827982792872"

and produce accurate output as a string;

assume any sane length of such input/output numbers (say less than 1 MB for string ;c)

it should cover addidtion, subtraction, multiplication and division (shoudl probably also gave rest from division)

code could be compared for
1) length
2) overal style
3) efficiency

[fir]

i guess normal coder, i mean medium-level and up could write it in one evening/ half-of day probably (assuming simple non optimised version) so it dont seem to be too complex [as i said only integers though signed]

it could be also somewhat profitable in some learning opportunities, so if "anton shepelev" would state it as a contest and
it would gain some acceptance and termin would be say next friday, i could probbaly p[articipate

[Thiago Adams]

Can I publish my code for review here? Maybe this is better
than context because I think for bignums the algorithm will
be similar.
The context can be for something that involves more
creativity and where solutions can differ more.

[fir]

not now,
similiar but not the same.. there is a spece to code things differently

i dont know if it topic will be taken
and this contest really run (dont depend on me it depends on amount of participants) but if so you should post it after then

so at least wait a few days - after that if you give some commentary i could be iven interested to see it... but the contest when i would have opportunity to
not only read but write something would
be of more use imo

[Robert Wessel]

On Fri, 31 Aug 2018 17:14:53 +0300, Anton Shepelev
<anton.txt@g{oogle}mail.com> wrote:

>fir:
>
>>small library for basic bignum (N*long) arithmetic
>
>Am I wrong in thinking that a trivial implementation is
>possible that stores numbers as byte arrays and treats them
>numbers in base 256? Futhermore, one may encode rational
>numbers losslessly storing numerator and denominator
>separately as such bignums.

Sure, but for a trivial implementation, it's just as easy to pick a
limb* that's half the width of the longest type that's convenient to
use. So if you have unsigned long longs that are 64 bits, and
unsigned longs that are 32, using 32 bit limbs is just as easy any a
smaller value, and yet leaves you with the ability to easily catch
carries, leaves room for carry propagation, and allow you to use the
widest multiplier (since the result will then fit in the 64 bit type).

Admittedly picking the types for the limb and double-limb sized
elements is not easy to do optimally if you can rely only on standard
C. You *could* just do all the intermediate calculations in unsigned
long longs, and store limbs in unsigned longs, while assuming that you
have a 64-bit intermediate format and a 32 bit storage format. While
that will work, it may waste considerable storage if that assumption
about sizes is not true (most LP64 platforms, for example), and does
not take advantage of larger sizes (for example, many GCC platforms
have a 128-bit type, which may be useful for the intermediate
operations).

The resulting algorithms for addition, subtraction and multiplication
are trivial (heck, I've posted them a few times over the years). Half
a dozen lines for addition, a dozen for multiplication (for unsigned
numbers, and punting memory management to elsewhere).

For larger numbers there are more complex techniques that can run
faster then the O(n**2) schoolbook multiplication algorithm (Karatsuba
- ~O(n**1.6), FFTs - O(n*log n*log(log n)) ), but at the expense of
complexity. Karatsuba is not that complex, and can be worthwhile for
numbers of 4-8 limbs or larger. FFTs are rather complex, and are not
really a net gain until you get to (at least) hundreds of limbs.

Division is something of a PITA no matter what, though. It's not
hard, per-se, but the only (near) trivial algorithm is really slow,
and the best depend on a mast implementation of multiplication.

You can use larger limbs (relative to the maximum "convenient" size),
but it adds a non-trivial amount of complexity. OTOH, sticking with
the half-maximum-width limbs is pretty much free, and will usually
perform much better than using bytes.


*limb = the effective bignum digit/base you're working in.