Re: jak posortować czynniki

Newsgroups	pl.comp.programming
Date	2016-10-14 09:10 -0700
References	(2 earlier) <adce70d3-d778-4af5-811c-51e0ecf4223b@googlegroups.com> <ntlujd$7ku$1@node2.news.atman.pl> <3d8269ff-fb2d-4bfc-a285-e1b18e3cb1ab@googlegroups.com> <ntm5rn$3p5$1@node1.news.atman.pl> <d00b2f80-aa46-48b0-98fc-a82bdca47e4c@googlegroups.com>
Message-ID	<bbf7f5c4-e480-409c-91a2-d4964fb79042@googlegroups.com> (permalink)
Subject	Re: jak posortować czynniki
From	bartekltg <bartekltg@gmail.com>

Show all headers | View raw

On Thursday, October 13, 2016 at 3:41:25 PM UTC+2, M.M. wrote:

> 
> Dzięki za odpowiedź, najbardziej przyda się pomysł
> który mi podsunąłeś, żeby wyciągać eksponenty :)
> Resztę w miarę ogarniam.

> Mam takie liczby do wymnożenia, że przy 80 losowo wybranych
> często pada. Liczby, choć nie służą do wyliczenia dwumianiu
> newtona, to powstają z dużych dodatnich i ujemnych potęg, więc 
> mogą po wymnożeniu nawet dać coś w okolicach jedynki. Napisałem
> najpierw podobnie do sortowania. Czynniki mam w kilku wektorach,
> jeśli w jednym mam czynniki duże, to w drugim mam małe, albo
> na odwrót. S skrócie: próbuję wymnożyć przez jedną, potem przez 
> drugą i wybieram tę, która daje wynik bliższy jedynce. Po tym 
> zabiegu mogę wymnożyć nawet 400 liczb bez problemów z zakresem, a
> nie muszę sortować. Jednak pomysł z przeniesieniem wykładników 
> do osobnej zmiennej zapewne będzie najlepszy i szybki.

Zrobiłem mały test
http://pastebin.com/3mWyh93z

Mnożenie bezpośrednie (najczęśceij daje 0 lub inf ;-))
Dodanie logartrymów - po to, aby sprawdzić wynik. Niestabilne!
Ale daje wynik i wiadomo, że sie nie pomyliśmy.

Prawdziwe algorytmy:

Jeden to modyfikacja sortowania. Nie potrzeba nam przecież
sortować, wystarczy zrobić podział na > 1 i < 1.
Potem mnożymy, jeśli tymczasowy wynik jest >1, korzystamy
ze zbioru liczb mniejszych, jeśli mniejszy, z większych.
Potem trzeba domnożyć ogon.

Rozwinięciem tego jest zrobienie partition i mnożenia na raz.
Mam dwa iteratory, jeden omija wszystkie <1, drugi omija
wszystko co jest >1.
Dalej tak samo, używam tego z przecinwej strony niz wynik.

Różnica jest minimalna. 
frexp jest ponad 2 razy szybszy!

W sumie mogliśmy się tego spodziewać. W obu wersjach 'sortujących'
mamy dwa przebiegi po tablicy, dla frexp tylko jeden,
a to dostęp do pamięci, a nie operacje będą wąskim gardłem. 

Chyba, że masz tylko tyle liczb, ile się mieści w cache. 
Wtedy... kto wie, trzeba by mój test nieco przerobić. 

pzdr
bartekltg

Back to pl.comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

jak posortować czynniki "M.M." <mmarszik@gmail.com> - 2016-10-12 08:41 -0700
  Re: jak posortować czynniki bartekltg <bartekltg@gmail.com> - 2016-10-12 18:42 +0200
    Re: jak posortować czynniki "M.M." <mmarszik@gmail.com> - 2016-10-12 10:55 -0700
      Re: jak posortować czynniki bartekltg <bartekltg@gmail.com> - 2016-10-12 20:15 +0200
        Re: jak posortować czynniki "M.M." <mmarszik@gmail.com> - 2016-10-12 11:59 -0700
          Re: jak posortować czynniki bartekltg <bartekltg@gmail.com> - 2016-10-12 22:19 +0200
            Re: jak posortować czynniki "M.M." <mmarszik@gmail.com> - 2016-10-13 06:41 -0700
              Re: jak posortować czynniki bartekltg <bartekltg@gmail.com> - 2016-10-14 09:10 -0700

csiph-web