Path: ...!news.mixmin.net!proxad.net!feeder1-2.proxad.net!cleanfeed1-b.proxad.net!nnrp1-2.free.fr!not-for-mail
Date: Sun, 15 Oct 2023 19:20:48 +0200
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: TV Zap
Content-Language: fr
References: <651dbae6$0$7463$426a74cc@news.free.fr>
 <651dbde7$0$3002$426a34cc@news.free.fr>
 <6521c78c$0$6424$426a34cc@news.free.fr>
 <65223edb$0$6100$426a74cc@news.free.fr>
 <6523908a$0$25947$426a74cc@news.free.fr>
 <6525082a$0$25967$426a74cc@news.free.fr>
 <6525a887$0$7786$426a74cc@news.free.fr> <E5f9ZvaLBYMNYI4J2VhFPbWk0zs@jntp>
From: Samuel Devulder <samuel.devulder@laposte.net.inalid>
Newsgroups: fr.sci.maths
In-Reply-To: <E5f9ZvaLBYMNYI4J2VhFPbWk0zs@jntp>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Antivirus: Avast (VPS 231015-4, 15/10/2023), Outbound message
X-Antivirus-Status: Clean
Lines: 37
Message-ID: <652c1f70$0$25949$426a74cc@news.free.fr>
Organization: Guest of ProXad - France
NNTP-Posting-Date: 15 Oct 2023 19:20:48 CEST
NNTP-Posting-Host: 88.167.72.245
X-Trace: 1697390448 news-3.free.fr 25949 88.167.72.245:22149
X-Complaints-To: abuse@proxad.net
Bytes: 2477

Le 15/10/2023 à 09:43, pehache a écrit :

> C'est comme une multiplication de matrice n*n : une fois n fixé c'est en 
> O(1) :)

Au *second degré* oui (en un sens (*)), mais ici on est au premier:

Si on pose:

	Fav(.,c) = a*c + b [mod N]

on entre dans les générateurs aléatoires congruentiels *linéaires*.
___
(*) Linéaires, pas quadratiques :)

Et alors
         Far(.,c) = Fav^(N-1)
                  = (b*(a^(N-1)-1)/(a-1) + c*a^(N-1) [mod n]
                  = b*(a^(N-2)+...+a²+a+1) + c*a^(N-2) [mod N]
                  = A*c + B [mod N]
avec
                A = a^(n-1) [mod N]
et             B = a^(N-2)+...+a²+a+1) + c*a^(N-2) [mod N]

qui peuvent tous deux être précalculés et sont de taille comparable aux 
a et b de départ, donnant alors un temps de calcul de Far() strictement 
identique à celui de Fav().

Comme déjà dit: une composition d'opérations linéaires en arithmétique 
modulaire est une autre opération linéaire modulaire. Ca ne change pas 
de complexité.

Avec ces générateurs et des a et b bien choisis, on a un mélange bien 
meilleur qu'une simple addition modulaire. Ta solution avec S=7 
correspond à a=0, b=7 qui est un mélange plus faible.

sam.